算法王晓东3-10汽车加油行驶问题完全解决

#include<stdio.h> #include<stdlib.h> int main() { int N,K,A,B,C; int work[100][100][12]; int map[100][100]; int min; int i,j,p,q,x,y,z; int s[4][3]; FILE *fp; fp=fopen("car7.in","r"); fscanf(fp,"%d%d%d%d%d",&N,&K,&A,&B,&C); for(i=0;i<N;i++) { for(j=0;j<N;j++) { fscanf(fp,"%d",&map[i][j]); } } 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++) for(z=0;z<=K+1;z++) work[i][j][z]=1000000; for(z=0;z<=K;z++) work[0][0][z]=0; y=1; while(y!=0) { y=0; for(i=0;i<N;i++) { for(j=0;j<N;j++) { if(i!=0||j!=0) { for(p=0;p<K+1;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(min<1000000) { if(work[i][j][p]>min+A*map[i][j]) y++; work[i][j][p]=min; if(map[i][j]==1) { work[i][j][0]+=A; for(x=1;x<=K;x++) work[i][j][x]=work[i][j][0]; break; } } else { work[i][j][p]=work[i][j][0]+C+A; for(x=p+1;x<=K;x++) work[i][j][x]=work[i][j][p]; break; } } } } } } printf("%d\n",work[N-1][N-1][0]); system("pause"); return 0; }