中国象棋中的跳马问题
时间限制: 2 Sec 内存限制:128 MB
题目描述
现在棋盘的大小不一定，由p，q给出，并且在棋盘中将出现障碍物（限制马的行动，与象棋走法相同）
输入
第一行输入n表示有n组测试数据。
每组测试数据第一行输入2个整数p,q，表示棋盘的大小(1<=p,q<=100)。
每组测试数据第二行输入4个整数，表示马的起点位置与终点位置。(位置的取值范围同p,q)
第三行输入m表示图中有多少障碍。
接着跟着m行，表示障碍的坐标。
输出
马从起点走到终点所需的最小步数。
如果马走不到终点，则输入“can not reach!”
样例输入
2
9 10
1 1 2 3
0
9 10
1 1 2 3
8
1 2
2 2
3 3
3 4
1 4
3 2
2 4
1 3
样例输出
1
can not reach!
思路：一开始把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入队列，这里需要一个数组用来记录此点在之前是否已经加入队列，如果加入过队列当中，就不需要再加入了，直到队列里的元素为空，或者搜索到了终点，搜索即停止，然后输出相应答案即可。
#include<stdio.h> #include<string.h> #include<queue> #include<iostream> using namespace std; int p,q; int sx,sy,ex,ey; int n,k,vis[111][111]; int hash[111][111]; int dx[]={2,2,-1,1,-2,-2,-1,1}; int dy[]={-1,1,-2,-2,-1,1,2,2}; struct nd { int x,y,t; }; int bfs() { nd bmp,bemp; bemp.x=sx; bemp.y=sy; bemp.t=0; queue<nd>que; //定义一个队列 que.push(bemp); //将bemp进队 while(!que.empty())//队列非空 { bemp=que.front(); //得到对首元素 que.pop(); //将对首元素出队 if(bemp.x==ex&&bemp.y==ey) return bemp.t; int xx; int yy; for(int i=0;i<8;i++) { int pp=i/2; if(pp==0) if(bemp.x+1<=p&&vis[bemp.x+1][bemp.y]==-1) continue; if(pp==1) if(bemp.y-1>=1&&vis[bemp.x][bemp.y-1]==-1) continue; if(pp==2) if(bemp.x-1>=1&&vis[bemp.x-1][bemp.y]==-1) continue; if(pp==3) if(bemp.y+1<=q&&vis[bemp.x][bemp.y+1]==-1) continue; xx=bemp.x+dx[i]; yy=bemp.y+dy[i]; if(xx>=1&&xx<=p&&yy>=1&&yy<=q&&vis[xx][yy]==0&&hash[xx][yy]==0) { bmp.x=xx; bmp.y=yy; bmp.t=bemp.t+1; que.push(bmp); hash[xx][yy]=-1; } } } return -1; } int main() { while(scanf("%d",&n)!=EOF) { while(n--) { scanf("%d%d",&p,&q); scanf("%d%d%d%d",&sx,&sy,&ex,&ey); memset(vis,0,sizeof(vis)); memset(hash,0,sizeof(hash)); int i,ox,oy; scanf("%d",&k); for(i=0;i<k;i++) { scanf("%d %d",&ox,&oy); vis[ox][oy]=-1; } int ans=bfs(); if(ans>=0) printf("%d\n",ans); else printf("can not reach!\n"); } } return 0; }
