本文主要是介绍POJ 1915(与HDU 1372类似,BFS代码都差不多),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
简单的BFS,因为做过HDU 1372,所以做这题没用几分钟,代码类似……#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int a,b,c,d,t,v[305][305],dist[8][2]={1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1,-1,-2};
struct abc
{int x,y,p;
};
int check(int x,int y)
{if(x>=0&&x<t&&y>=0&&y<t) return 1;return 0;
}
int bfs()
{if (a==c&&b==d) return 0;memset(v,0,sizeof(v));queue<abc>q;abc t,s;t.x=a; t.y=b; t.p=0;v[a][b]=1;q.push(t);while(!q.empty()){t=q.front();q.pop();for(int i=0;i<8;i++){s.x=t.x+dist[i][0];s.y=t.y+dist[i][1];if(!v[s.x][s.y]&&check(s.x,s.y)){s.p=t.p+1;if(s.x==c&&s.y==d) return s.p;v[s.x][s.y]=1;q.push(s);}}}
}
int main()
{int n;cin>>n;while(n--){cin>>t>>a>>b>>c>>d;cout<<bfs()<<endl;}return 0;
}
这篇关于POJ 1915(与HDU 1372类似,BFS代码都差不多)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!