本文主要是介绍POJ-1915 Knight Moves 简单搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 305;
const int inf = 1<<30;
int n,m;
int map[maxn][maxn];
int xs[] = {1,-1,1,-1,2,2,-2,-2};
int ys[] = {2,2,-2,-2,1,-1,1,-1};
struct node
{int x,y,step;
};
void BFS( node s,node e )
{node cur,cnt;queue<node>que;memset(map,-1,sizeof(map));s.step = map[s.x][s.y] = 0;que.push(s);while( !que.empty() ){cur = que.front(); que.pop();if( cur.x == e.x && cur.y == e.y )return;for( int i = 0; i < 8; i ++ ){cnt.x = cur.x + xs[i];cnt.y = cur.y + ys[i];if( cnt.x >= 0 && cnt.x < n && cnt.y >= 0 && cnt.y < n && map[cnt.x][cnt.y] == -1 ){cnt.step = cur.step + 1;map[cnt.x][cnt.y] = cnt.step;if( cnt.x == e.x && cnt.y == e.y )return;que.push(cnt);}}}
}
int main()
{//freopen("data.txt","r",stdin); int cas;node s,e;scanf("%d",&cas);while( cas -- ){scanf("%d",&n);scanf("%d%d",&s.x,&s.y);scanf("%d%d",&e.x,&e.y);BFS(s,e);printf("%d\n",map[e.x][e.y]);}return 0;
}
这篇关于POJ-1915 Knight Moves 简单搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
