汽车加油行驶问题（习题3-16）

问题描述：

给定一个N*N 的方形网格，设其左上角为起点，坐标为（1，1），X 轴向右为正，Y 轴向下为正，每个方格边长为1。一辆汽车从起点出发驶向右下角终点，其坐标为（N，N）。

在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：

（1）汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。

（2）当汽车行驶经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B，否则免付费用。

（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。

（4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。

（5）(1)～(4)中的各数N、K、A、B、C均为正整数。

算法设计：

求汽车从起点出发到达终点的一条所付费用最少的行驶路线。

-Driving automobile fuel problem (Exercise 3-16)

Problem descr iption:

Given an N* N square grid, set the upper left corner as a starting point, coordinates (1,1), X-axis to the right is positive, Y axis under

Positive side of each square is 1. A car starting from the starting point towards the lower right corner of the end, the coordinates (N, N).

In a number of grid intersection points, set the oil tanks, fuel for the car is moving his way. Car in motion the process to be observed, such as

The following rules:

(1) The car can only travel along the grid edge, full of oil can travel the grid section K edge. Starting when the car was filled with oil, in the beginning and the end

No point depot.

(2) When the vehicle driving through a mesh edge, if the X coordinate or Y coordinate decreases, the fees payable B, or toll-free

Use.

(3) vehicles in the process of moving the event should fill up and pay for fuel oil storage costs A.

(4) when required grid points in the addi