首页 > 代码库 > POJ - 1915 Knight Moves
POJ - 1915 Knight Moves
BFS结合队列
#include<stdio.h>#include<string.h>#include<queue>using namespace std;int x,y,l;const int maxn=300+5;int visit[maxn][maxn];struct node{ int xpos; int ypos; int cur; void init(int x,int y,int d) { xpos=x;ypos=y;cur=d; }};int bfs(node source,node target);int main(){ int n; scanf("%d",&n); while(n--){ scanf("%d",&l); node start; node end; scanf("%d%d",&start.xpos,&start.ypos); scanf("%d%d",&end.xpos,&end.ypos); int minsteps=bfs(start,end); printf("%d\n",minsteps); } return 0;}int bfs(node source,node target){ int dir[10][5]={{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}}; source.cur=0; queue<node>temp; temp.push(source); memset(visit,0,sizeof(visit)); visit[source.xpos][source.ypos]=1; if(source.xpos==target.xpos && source.ypos==target.ypos) return 0; while(!temp.empty()){ node c=temp.front(); x=c.xpos; y=c.ypos; for(int i