2005年上海交通大学计算机研究生机试真题
发布时间
阅读量：
阅读量
题目1091：棋盘游戏
题目描述：
有一个6*6的棋盘，每个棋盘上都有一个数值，现在又一个起始位置和终止位置，请找出一个从起始位置到终止位置代价最小的路径：
1、只能沿上下左右四个方向移动
2、总代价是没走一步的代价之和
3、每步（从a,b到c,d）的代价是c,d上的值与其在a,b上的状态的乘积
4、初始状态为1
每走一步，状态按如下公式变化：（走这步的代价%4）+1。
输入：
第一行有一个正整数n，表示有n组数据。
每组数据一开始为6*6的矩阵，矩阵的值为大于等于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算法分析：DFS算法。
#include<iostream>
#include<string.h>
using namespace std;
int p,q,mins; //(p,q)是终止坐标
int a[51][51],state ,book[51][51];//a数组存储每个位置的值，state存储每个位置的状态，book表示是否访问过
int next[4][2]={{0,1},//向右
{1,0},//向下
{0,-1},//向左
{-1,0} };//向上
void dfs(int x,int y,int state,int cost)//dfs的作用是用来处理当前这一步怎么走
{
int tx,ty,k,sum;
if(x==p&&y==q)//到达小红位置
{
if(cost<mins)
mins=cost;
return ;
}
if(cost>mins)//没有这个剪枝判断就会超时。
return ;
//未到达位置向四个方向走
for(k=0;k<=3;k++)
{
//计算下一个点坐标
tx=x+next[k][0];
ty=y+next[k][1];
//判断是否越界
if(tx<0||tx>=6||ty<0||ty>=6)
continue;
//判断是否已经在路径中
if(book[tx][ty]==0)
{
book[tx][ty]=1;//标记这个点已经走过
sum=a[tx][ty]*state;//这一步的代价
dfs(tx,ty,sum%4+1,cost+sum);//开始尝试下一个点
book[tx][ty]=0;//尝试结束，取消标记
}
}
}
int main()
{
int i,j,startx,starty,n;//startx,starty是开始坐标
//freopen("datain.txt","r",stdin);
//freopen("dataout.txt","w",stdout);
cin>>n;
while(n--)
{
memset(book,0,sizeof(book));
mins=999999;
//当i从1-6结果就不对，从0-5就可以，因为终止循环条件if(x==p&&y==q)是x,y变化后刚刚到p,q，
//在p,q位置的处理并没有进行，如果i从1-6那么终止条件就要变化
for(i=0;i<6;i++)
for(j=0;j<6;j++)
cin>>a[i][j];//用二维数组存储矩阵的值
cin>>startx>>starty>>p>>q;
//book[startx][starty]=1;//标记起点防止重复走，但是保留这个语句的时候却是WA.
dfs(startx,starty,1,0);
cout<<mins<<endl;//输出最小代价
}
return 0;
}全部评论 (0)
还没有任何评论哟~