1. 题目源地址：http://ac.jobdu.com/problem.php?pid=1091
2. 源代码
（1）DFS方法：
#include<iostream>
#include<memory.h>
using namespace std;
int map[6][6];//定义棋盘
int visited[6][6];
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
int start_x,start_y,end_x,end_y;//定义起始和结束节点的坐标
int sum,status,ans;
bool InMap(int x,int y)
{
if(x>=0 && x<6 && y>=0 && y<6)
return true;
else
return false;
}
void DFS(int x,int y,int status,int sum)
{
int next_x,next_y,cost;
int i;
if(sum<ans)
{
if(x==end_x && y==end_y)
{
ans=sum;
return ;
}
for(i=0;i<4;i++)
{
next_x=x+dx[i];
next_y=y+dy[i];
if(!visited[next_x][next_y] && InMap(next_x,next_y))
{
cost=map[next_x][next_y]*status;//走到next_x,next_y要付出的代价
//status=cost%4+1;//走到next_x,next_y后的状态
//sum=sum+cost;//总代价
visited[next_x][next_y]=1;
DFS(next_x,next_y,cost%4+1,sum+cost);//注意：将cost%4+1和sum+cost作为参数传递
visited[next_x][next_y]=0;//注意：若是next_x,next_y走不通，一定要回退
}
}
}
}
int main()
{
int caseNum;
int i,j;
cin>>caseNum;
while(caseNum--)
{
memset(visited,0,sizeof(visited));
for(i=0;i<6;i++)
for(j=0;j<6;j++)
cin>>map[i][j];
cin>>start_x>>start_y>>end_x>>end_y;
ans=999999;
DFS(start_x,start_y,1,0); //初始状态为1,初始总代价为0
cout<<ans<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163044.html
