汽车加油行驶问题

1.问题描述

给定一个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均为正整数。

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

数据输入：
输入数据。第一行是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 个数以空格分隔。

结果输出:
将找到的最优行驶路线所需的费用，即最小费用输出.

Sample input

9 3 2 3 6
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

Sample output

12

 

2.动态规划算法的方程式

   work[i][j][p]表示由（0，0）到达（i,j）并且剩下汽油可走p段路程的最小代价。

   则work[i][j][p]=min{work[i+s[q][0]][j+s[q][1]][p+1]+s[q][2]},(q=0,1,2,3);

   其中，S[4][3]={{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}};

   只要有更新就重复计算

3.代码实现

  void main(){

 int N,K,A,B,C;
 int work[100][100][12],map[100][100];
 int i,j,p,q,r,min;
 FILE *fp;     
 fp=fopen("car2.txt","r");
 fscanf(fp,"%d%d%d%d%d",&N,&K,&A,&B,&C);
 int s[4][3];
 s[0][0]=-1;
 s[0][1]=0;    
 s[0][2]=0; 
 s[1][0]=0; 
 s[1][1]=-1;   
 s[1][2]=0;  
 s[2][0]=1;   
 s[2][1]=0; 
 s[2][2]=B; 
 s[3][0]=0; 
 s[3][1]=1; 
 s[3][2]=B;
 for(i=0;i<N;i++)
 { 
	 for(j=0;j<N;j++) 
	 { 
		 fscanf(fp,"%d",&map[i][j]); 
	 }
 }

 for(i=0;i<N;i++)  
 {
	 for(j=0;j<N;j++)         
	 { 
		 for(p=0;p<=K+1;p++) 
		 {          
			 work[i][j][p]=1000000;    
		 }
	 }
 }

 for(i=0;i<=K;i++)     
 {
	 work[0][0][i]=0;    
 }
 r=20;   
 while(r>0) 
 {
	 r=0;
	 for(i=0;i<N;i++)        
	 {
		 for(j=0;j<N;j++)
		 {   
			 if(i!=0||j!=0)   
			 {
				 for(p=0;p<=K;p++)
				 {        
					 min=1000000;   
					 for(q=0;q<4;q++)
					 {       
						 if(i==0&&q==0)   
							 continue;   
						 if(j==0&&q==1)     
							 continue;       
						 if(i==N-1&&q==2)       
							 continue;     
						 if(j==N-1&&q==3)  
							 continue;    
                         if(work[i+s[q][0]][j+s[q][1]][p+1]+s[q][2]<min)  
						 {
							 min=work[i+s[q][0]][j+s[q][1]][p+1]+s[q][2];
						 }
					 }
					 if(work[i][j][p]>min+map[i][j]*A)    
					 {
						 r++;   
					 }
					 work[i][j][p]=min;     
					 if(map[i][j]==1)
					 {  
						 work[i][j][p]+=A;     
						 for(q=1;q<=K;q++)   
							 work[i][j][q]=work[i][j][0]; 
						 break;     
					 }else if(work[i][j][p]==1000000)
					 {
						 work[i][j][p]=work[i][j][0]+C+A;
						 for(q=p+1;q<=K;q++)     
						 {
							 work[i][j][q]=work[i][j][p]; 
						 }
						 break;
					 }
				 }
			 }
		 }
	 }
 }

  printf("%d\n",work[N-1][N-1][0]);  
  FILE *fout;
  fout=fopen("output2.txt","w");
  fprintf(fout,"%d\n",work[N-1][N-1][0]);
  fclose(fout);
}

 

4。对于解这个问题，我还是不怎么明白，真是纠结啊！那位朋友看到了这篇文章，感觉有所想法的话，可以留下言啊，谢谢！