POJ 2243 Knight Moves(BFS实现或DFS实现)
http://poj.org/problem?id=2243
题意:一个8*8的中国象棋棋牌,给你两个坐标,问你马从起点走到终点最少需要几步.(马可以朝4个方向8种走法,只能走日字,具体见代码)
分析:通过该题的DFS实现和上一题DFS实现,我们可以了解到,只要我们能合理的剪枝,就能使DFS递归收敛.所以不要怀疑DFS的正确性.
首先用BFS实现.
AC代码: 0ms
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=10;
int r1,c1,r2,c2;
struct Node
{
int r,c;
Node(int r,int c):r(r),c(c){}
};
int vis[maxn][maxn];
int dist[maxn][maxn];
queue<Node> Q;
int dr[]={-2,-2,-1,-1,1,1,2,2};
int dc[]={-1,1,2,-2,2,-2,1,-1};
int BFS()
{
if(r1==r2&&c1==c2) return 0;
while(!Q.empty()) Q.pop();
memset(vis,0,sizeof(vis));
vis[r1][c1]=1;
dist[r1][c1]=0;
Q.push(Node(r1,c1));
while(!Q.empty())
{
Node node=Q.front();Q.pop();
int r=node.r,c=node.c;
for(int d=0;d<8;d++)
{
int nr=r+dr[d];
int nc=c+dc[d];
if(nr>=0&&nr<8 && nc>=0 &&nc<8 &&vis[nr][nc]==0)
{
if(nr==r2&&nc==c2) return dist[r][c]+1;
dist[nr][nc]=1+dist[r][c];
Q.push(Node(nr,nc));
vis[nr][nc]=1;
}
}
}
return -1;
}
int main()
{
char str1[10],str2[10];
while(scanf("%s%s",str1,str2)==2)
{
r1=str1[1]-'1';
c1=str1[0]-'a';
r2=str2[1]-'1';
c2=str2[0]-'a';
printf("To get from %s to %s takes %d knight moves.\n",str1,str2,BFS());
}
return 0;
}
AC代码: DFS实现 63ms
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=10;
int r1,c1,r2,c2;
struct Node
{
int r,c;
Node(int r,int c):r(r),c(c){}
};
int vis[maxn][maxn];
int dist[maxn][maxn];
queue<Node> Q;
int dr[]={-2,-2,-1,-1,1,1,2,2};
int dc[]={-1,1,2,-2,2,-2,1,-1};
int ans;//最终答案
void DFS(int r,int c,int len)
{
if(ans<=len || r<0 || r>=8 || c<0 || c>=8) return ;//剪枝
if(r==r2&&c==c2) ans=min(ans,len);
if(vis[r][c]==0 || (dist[r][c]>len))
{
vis[r][c]=1;
dist[r][c]=len;
}
else if(vis[r][c]==1 && len >= dist[r][c] )
return ;
for(int d=0;d<8;d++)
{
int nr=r+dr[d];
int nc=c+dc[d];
DFS(nr,nc,len+1);
}
}
int main()
{
char str1[10],str2[10];
while(scanf("%s%s",str1,str2)==2)
{
r1=str1[1]-'1';
c1=str1[0]-'a';
r2=str2[1]-'1';
c2=str2[0]-'a';
memset(vis,0,sizeof(vis));
ans=10;
DFS(r1,c1,0);
printf("To get from %s to %s takes %d knight moves.\n",str1,str2,ans);
}
return 0;
}
分享到:
相关推荐
该题求解从一个坐标到达另一个坐标的最短步数,移动规则需要按照题目给的方式来移动,即按照国际象棋马的走法一致。
北大 acm JudgeOnline poj1915 Knight Moves c++源代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
北大POJ1020-Anniversary Cake 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索技巧和剪枝 POJ 1010 :star: POJ 2362 POJ 1011(搜索+剪枝) POJ 1416 POJ 2676 POJ 1129:white_question_...
POJ 3131 双向BFS解立体八数码问题
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码