hdu 1372 Knight Moves(经典BFS)

本文主要是介绍hdu 1372 Knight Moves(经典BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1372

大意：至少要用多少步，骑士才能从给定位置到达另一个位置。（骑士的走法和象棋里的马的走法是一样的，均是日字型）

Sample Input

  e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

Sample Output

  To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

显然，这需要BFS。

BFS核心是一次性先把所有最近的能走的统统遍历，然后再去遍历其他的点。这和队列联系在一起了，近点先进，远点后进，对队列的遍历就相当于层次遍历了。比如这个二叉树的层次遍历：

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool vis[9][9];
int s[2],e[2];
int dir[8][2]={{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-1,2},{-2,1}};
typedef struct node{int x,y,step;  //pre[]
}Node;
Node que[90];
int bfs(int sx,int sy){int l=0,r=0;vis[sx][sy]=1;que[r].x=sx;que[r].y=sy;que[r++].step=0;while(l<r){Node cur=que[l++],next;for(int i=0;i<8;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];next.step=cur.step+1;if(next.x>=1&&next.x<=8&&next.y<=8&&next.y>=1&&!vis[next.x][next.y]){if(next.x==e[0]&&next.y==e[1]){  return next.step; }vis[next.x][next.y]=1;que[r++]=next;}}}return 0;
}
int main()
{//freopen("cin.txt","r",stdin);char start[5],end[5];while(cin>>start>>end){s[0]=start[0]-'a'+1; //加1啊，不要犯错。s[1]=start[1]-'0';e[0]=end[0]-'a'+1;e[1]=end[1]-'0';memset(vis,0,sizeof(vis));memset(que,0,sizeof(que));printf("To get from %s to %s takes %d knight moves.\n",start,end,bfs(s[0],s[1]));}return 0;
}

这篇关于hdu 1372 Knight Moves(经典BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！