42
技術社區[雲棲]
九度題目1091：棋盤遊戲
題目1091：棋盤遊戲
時間限製：1 秒
內存限製：32 兆
特殊判題：否
提交：1081
解決：260
題目描述：
有一個66的棋盤，每個棋盤上都有一個數值，現在又一個起始位置和終止位置，請找出一個從起始位置到終止位置代價最小的路徑：
1、隻能沿上下左右四個方向移動
2、總代價是沒走一步的代價之和
3、每步（從a,b到c,d）的代價是c,d上的值與其在a,b上的狀態的乘積
4、初始狀態為1
每走一步，狀態按如下公式變化：（走這步的代價%4）+1。
輸入：
第一行有一個正整數n，表示有n組數據。
每組數據一開始為66的矩陣，矩陣的值為大於等於1小於等於10的值，然後四個整數表示起始坐標和終止坐標。
輸出：
輸出最小代價。
樣例輸入：
1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 5 5
樣例輸出：
23
來源：
2005年上海交通大學計算機研究生機試真題
就是這麼寫，DFS，為什麼一直WA，找不出原因......查了標準程序，一模一樣啊.....
代碼：
#includestdio.h
#includestring.h
int map[8][8];
int flag[8][8];
int max,s1,s2,e1,e2;
#define INF 10000000
void Found(int state,int x,int y,int sum)
{
if(x==e1&&y==e2)
{
if(summax)
max=sum;
return;
}
if(summax) return;剪枝優化
if(xe1ye2) return;
if(x+16&&flag[x+1][y]==0)下
{
flag[x+1][y]=1;
Found((statemap[x+1][y])%4+1,x+1,y,sum+statemap[x+1][y]);
flag[x+1][y]=0;
}
if(x-1=0&&flag[x-1][y]==0)上
{
flag[x-1][y]=1;
Found((statemap[x-1][y])%4+1,x-1,y,sum+statemap[x-1][y]);
flag[x-1][y]=0;
}
if(y+16&&flag[x][y+1]==0)右
{
flag[x][y+1]=1;
Found((statemap[x][y+1])%4+1,x,y+1,sum+statemap[x][y+1]);
flag[x][y+1]=0;
}
if(y-1=0&&flag[x][y-1]==0)左
{
flag[x][y-1]=1;
Found((statemap[x][y-1])%4+1,x,y-1,sum+statemap[x][y-1]);
flag[x][y-1]=0;
}
}
int main()
{
int i,j,n,m,state;
scanf(%d,&n);
while(n--)
{
memset(flag,0,sizeof(flag));
for(i=0;i6;i++)
{
for(j=0;j6;j++)
{
scanf(%d,&map[i][j]);
}
}
scanf(%d%d%d%d,&s1,&s2,&e1,&e2);
state=1;max=INF;
Found(state,s1,s2,0);
printf(%dn,max);
}
return 0;
}
最後更新：2017-04-03 12:56:20