首页 > 代码库 > hdu 1372 knight Moves
hdu 1372 knight Moves
Knight Moves
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6458 Accepted Submission(s): 3900
题意:在一个8*8的棋盘上给出起始位置和终点用骑士去走其实只能按照国际象棋的规定走要求输出最短路径的大小
简单bfs直接套模板
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; int ya,yb,vis[10][10]; int ans; char a[3],b[3]; struct node{ int a,b,depth;//depth记录走的步数 }; int d[8][2]={-2,1, -1,2, 1,2, 2,1, 2,-1, 1,-2, -1,-2, -2,-1}; void bfs(int x,int y) { int i; node t,p; queue<node> q; t.a=x; t.b=y; t.depth=0; vis[t.a][t.b]=1; q.push(t); while(!q.empty()) { t=q.front(); q.pop(); if(t.a==ya&&t.b==yb) { printf("To get from %s to %s takes %d knight moves.\n",a,b,t.depth); return ; } for(i=0;i<8;i++) { p.a=t.a+d[i][0]; p.b=t.b+d[i][1]; if(p.a>0&&p.a<=8&&p.b>0&&p.b<=8&&!vis[p.a][p.b]) { p.depth=t.depth+1; q.push(p); } } } } int main() { int xa,xb; while(~scanf("%s%s",&a,&b)) { ans=0; xa=a[0]-'a'+1;ya=b[0]-'a'+1; xb=a[1]-'0';yb=b[1]-'0'; memset(vis,0,sizeof vis); bfs(xa,xb); } return 0; }
hdu 1372 knight Moves
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。