#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);
}
评论0