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