汽车行驶加油问题： 3-16：给定一个N*N 的方形网格，设其左上角为起 点S，坐标为（1，1），X 轴向右为正，Y 轴向下为正，每个方格边长为1。一辆汽车从起点S出发驶向右下角终点T，其坐标为（N， N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则： （1）汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。 （2）当汽车行驶经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B;否则免付费用。,（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。 （4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。 其中，(1)(4) 中的各数N、K、A、B、C 均为正整数。 试设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。,分析与解答： 用f(x,y,0)表示汽车从网格点(1,1)行驶到网格点(x,y)所需的最少费用，f(x,y,1)表示汽车行驶至网格点(x,y)后还能行驶的网格边数。 建立计算f(x,y,o)和f(x,y,1)递归式如下： f(1,1,0)=0,f(1,1,1)=K f(x,y,0)=f(x,y,0)+A，f(x,y,1)=K,(x,y)是油库 f(x,y,0)=f(x,y,0)+C+A，f(x,y,1)=K,(x,y) 非油库且f(x,y,1)=0 f(x,y,0)=minf(x+si0,y+si1,0)+si2 0=i4 f(x,y,1)=f(x+sj0,y+sj1,1)-1 其中，数组s=-1,0,0,0,-1,0,1,0,B,0,1,B.,using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 汽车动态规划.Net3._5版 public class Driving private static int A = 2; private static int B = 3; private static int C = 6; private static int K = 3; private static int N = 9; private static int MAX = 100000000; private static int, S = -1, 0, 0 , 0, -1, 0 , 1, 0, B , 0, 1, B ; static int len = K; /* * 私有变量 */ private int, f;/记录状态 private int, p;/油库点 /* * */,public Driving(int, p) / TODO Auto-generated constructor stub this.p = p; f = new intN + 1, N + 1; for (int i = 0; i N + 1; i+) for (int j = 0; j N + 1; j+) fi, j = MAX; f1, 1 = 0; /* * 使用备忘录方法自顶向下解决问题 */,public int driving2(int x, int y) if (x N | y N) return MAX; if (fx, y MAX) if (isOil(x, y) fx, y += A; len = K; else if (!isOil(x, y) /* * 查表没有查到 */,if (x = 1 ,private bool isOil(int x, int y) for (int i = 0; i p.GetLength(0); i+) if (pi, 0 = x ,using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace 汽车动态规划.Net3._5版 class Program static void Main(string args) int, p = 1, 5 , 2, 4 , 2, 6 , 2, 7 , 3, 1 , 3, 3 , 3, 8 , 4, 6 , 4, 9 , 5, 1 , 5, 4 , 5, 7 , 6, 2 , 6, 8 , 7, 5 , 7, 9 , 8, 1 , 8, 4 , 8, 8 , 9, 2 ; /int, p = 1, 2 ; Driving d = new Driving(p); Console.WriteLine(d.driving2(9, 9); Console.WriteLine(); ,数据输入： 由文件input.txt 提供输入数据。文件的第一行是N，K，A，B，C 的值，2 N 100， 2 K 10。第二行起是一个N*N 的0-1 方阵，每行N 个值，至N+1 行结束。方阵的第i 行第j 列处的值为1 表示在网格交叉点（i，j）处设置了一个油库，为0 时表示未设油库。各行相邻的2 个数以空格分隔。 结果输出: 程序运行结束时，将找到的最优行驶路线所需的费用，即最小费用输出到文件output.txt 中。文件的第1 行中的数是最小费用值。,输入文件示例 输出文件示例 input.txt output.txt output.txt 9 3 2 3 6 12 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0,知识回顾Knowledge Review,