题目 http://acm.hdu.edu.cn/showproblem.php?pid=1372
这是一个简单的搜索问题 题目意思是 一只马从一个点到另外一个点就可以了 你要知道象棋中马是怎么走的。
其他的就可以了,刚开始做这个题目的时候 ,由于标记数组为mark[9][9] 但是我在初始化的时候
for(int i=0;i<=9;i++) for(int j=0;j<=9;j++) { mark[i][j]=0; }
一直错了 就是不知道为什么 呵呵 所以一定要小心哦。。。
ac 代码
#include<iostream> #include<cstdio> #include<queue> using namespace std; struct node{ int x,y,num;};///num 步数 char s[5],s1[5]; int sx,sy,ex,ey,mark[9][9]; int dre[8][2]={1,2,1,-2,2,1,2,-1,-1,2,-1,-2,-2,1,-2,-1}; ///2,1,2,-1,-2,1,-2,-1,1,2,1,-2,-1,2,-1,-2 ///马走的坐标 void bfs() { for(int i=0;i<9;i++) ///标记初始化 for(int j=0;j<9;j++) { mark[i][j]=0; } queue<node> Q; node p,t; p.x=sx; p.y=sy; p.num=0; // int sum=0; mark[sx][sy]=1; Q.push(p); while(!Q.empty()) { t=Q.front(); Q.pop(); if(t.x==ex&&t.y==ey) ///是否到达目的地 { cout<<"To get from "<<s<<" to "<<s1<<" takes "<<t.num<<" knight moves."<<endl; return ; } for(int i=0;i<8;i++) ///马可以从8个方向走 { p=t; p.x+=dre[i][0]; p.y+=dre[i][1]; ///是否在棋盘里面 if(p.x>=0&&p.x<8&&p.y>=0&&p.y<8&&!mark[p.x][p.y]) { mark[p.x][p.y]=1; p.num+=1; Q.push(p); } } } } int main() { while(scanf("%s %s",s,s1)!=EOF) { sy=s[0]-'a',sx=s[1]-'1'; ///这样x,y的坐标 ey=s1[0]-'a',ex=s1[1]-'1'; if(sx==ex&&sy==ey) { cout<<"To get from "<<s<<" to "<<s1<<" takes 0 knight moves."<<endl; continue; } bfs(); } return 0; }