【题面】【我们都知道，在中国象棋中，马是走日字步的。现给定马的起始坐标与终点坐标，求出马最快能到达的路线。如果有多条路线都是步数最少的，则输出路线的数目。注意，此时棋盘上可能会有一些其它的棋子，这些棋子是会憋马脚的，注意！】
BFS好题。确实是好题。我出错的地方有几个：1、把蹩马脚的点和访问过的点混淆，应该分别标记；2、访问终点后将终点标记，而这题显然不能；3、标记路线的时候出了小差错。大概就这些。
#include<cstdio> #include<queue> #include<stack> #include<iostream> using namespace std; int G[18][18]; int dx[]= {-2,-2,2,2,-1,1,-1,1}; int dy[]= {-1,1,-1,1,-2,-2,2,2}; int method=0; struct Point { int x,y; int fa; int self; Point(){} Point(int _x,int _y,int _fa,int _self):x(_x),y(_y),fa(_fa),self(_self){} bool operator==(Point &tp) { if(tp.x==x&&tp.y==y) return true; return false; } }P[150]; int cnt=0; int bfs(Point start,Point &endz) { queue<Point> q; q.push(start); G[start.x][start.y]=1; int step=0; while(!q.empty()) { step++; int size=q.size(); while(size--) { Point now=q.front(); // cout<<now.x<<" "<<now.y<<" "<<now.fa<<" "<<now.self<<endl; q.pop(); for(int i=0; i<8; i++) { int nx=now.x+dx[i]; int ny=now.y+dy[i]; int mx=now.x+dx[i]/2; int my=now.y+dy[i]/2; // the point visited was flag and be seeing as the the 蹩马脚！！ if(nx>=0&&nx<=10&&ny>=0&&ny<=10&&G[mx][my]!=2&&!G[nx][ny]) { // cout<<nx<<" "<<ny<<endl; G[nx][ny]=1;//the cnt is starting from 2,but the P[2] is empty. P[cnt]=Point(nx,ny,now.self,cnt); cnt++; if(P[cnt-1]==endz) { G[nx][ny]=0; endz.fa=P[cnt-1].fa; method++; } else q.push(P[cnt-1]); } } } if(method>0) return step; } } int main() { freopen("a.txt","r",stdin); int x,y; scanf("%d%d",&x,&y); P[cnt++]=Point(x,y,0,0); scanf("%d%d",&x,&y); P[cnt++]=Point(x,y,-1,1); int M; scanf("%d",&M); for(int i=0; i<M; i++) { scanf("%d%d",&x,&y); G[x][y]=2; } if(P[0]==P[1]) {printf("0\n");return 0;} int step=bfs(P[0],P[1]); stack<Point> st; st.push(P[1]); int tot=P[1].fa; while(1) { st.push(P[tot]); // cout<<P[tot].x<<" "<<P[tot].y<<" "<<P[tot].fa<<endl; if(P[tot]==P[0]) break; tot=P[tot].fa; } if(method==1) { while(!st.empty()) { printf("(%d,%d)",st.top().x,st.top().y); st.pop(); if(st.size()!=0) printf("-"); } printf("\n"); } else { printf("%d\n",step); } }
转载于:https://www.cnblogs.com/Airplus/p/3868829.html
