guihua.zip_visual c

#include "stdio.h" #include "stdlib.h" #include "iostream.h" #include "iomanip.h" #define MIN(a,b) (a<b ? a:b) void main() { FILE *input; //打开输入数据文件以及要写入的文件 if((input=fopen("input.txt","r"))==NULL) { printf("the in file was not opened!\n"); exit(1); } FILE *output; if ((output=fopen("output.txt","w"))==NULL) { printf("the out file was not opened!\n"); exit(1); } int N,K,A,B,C; int i,j; fscanf(input,"%d %d %d %d %d",&N,&K,&A,&B,&C); int s[4][3]={-1,0,0,0,-1,0,1,0,B,0,1,B}; //定义来自每一个位置的状态 int **p; p=(int **)malloc((N+1)*sizeof(int *)); //定义所有位置的加油站的状态 for (i=0;i<=N;i++) { p[i]=(int *)malloc((N+1)*sizeof(int)); } for (i=0;i<=N;i++) { for (int j=0;j<=N;j++) { p[i][j]=0; } } for (i=1;i<=N;i++) //给每一个位置赋值 { for (j=1;j<=N;j++) { fscanf(input,"%d",&p[i][j]); cout<<p[i][j]<<' '; } cout<<endl; } typedef struct //定义来自哪一个节点 { int x; int y; }node; node **c; //申请来自哪一个节点的空间 c=(node **)malloc((N+1)*sizeof(node *)); for (i=0;i<N+1;i++) { c[i]=(node *)malloc((N+1)*sizeof(node)); } int ***f; //三维数组，记录最小费用以及还能行驶的路程 f=(int ***)malloc((N+1)*sizeof(int **)); for (i=0;i<N+1;i++) { f[i]=(int **)malloc((N+1)*sizeof(int **)); for (j=0;j<N+1;j++) { f[i][j]=(int *)malloc(2*sizeof(int *)); } } int k; for (i=1;i<=N;i++) { for (j=1;j<=N;j++) { f[i][j][0]=100; // cout<<f[i][j][0]<<' '; } // cout<<endl; } for (i=1;i<=N;i++) { for (j=1;j<=N;j++) { f[i][j][1]=K; // cout<<f[i][j][1]<<' '; } // cout<<endl; } f[1][1][0]=0; f[1][1][1]=K; int x; int y; int count=1; int tempx; int tempy; while(count) { count=0; for (x=1;x<=N;x++) //其实x为内层，y为外层，对应坐标以及s的坐标系 { for (y=1;y<=N;y++) { if (x==1&&y==1) { continue; } int min_temp=100; int temp; int tx,ty; int fhop; int minfhop; for (k=0;k<4;k++) { tx=x+s[k][0]; ty=y+s[k][1]; if (tx<1||tx>9||ty<1||ty>9) //边界检查！！ { continue; } temp=f[tx][ty][0]+s[k][2]; fhop=f[tx][ty][1]-1; if (p[x][y]==1) //有加油站 { temp+=A; fhop=K; } if ((fhop==0)&&(p[x][y]==0)&&(x!=N||y!=N)) //没有加油站，并且没有油了 { temp+=A+C; fhop=K; } if (temp<min_temp) //能够往前继续走 { min_temp=temp; minfhop=fhop; tempx=tx; tempy=ty; } } if (f[x][y][0]>min_temp) //如果发现周围有更好的解，则替换f,c等记录路径 { count++; f[x][y][0]=min_temp; f[x][y][1]=minfhop; c[x][y].x=tempx; c[x][y].y=tempy; } } } } for (i=1;i<N+1;i++) { for (j=1;j<N+1;j++) { cout<<setw(4)<<f[j][i][0]; } cout<<endl; } cout<<f[9][9][0]<<endl; x=9; y=9; while ((x!=1)||(y!=1)) { int tempx; printf("(%d,%d),%d\n",x,y,f[x][y][0]); tempx=x; x=c[x][y].x; y=c[tempx][y].y; } printf("(%d,%d),%d\n",x,y,f[x][y][0]); free(c); free(p); }