C++——跳马问题(广搜)
跳马
时限:1000ms 内存限制:10000K 总时限:3000ms
描述:
在国际象棋中,马的走法与中车象棋类似,即俗话说的“马走日”,下图所示即国际象棋中马(K)在一步能到达的格子(其中黑色的格子是能到达的位置)。
现有一200*200大小的国际象棋棋盘,棋盘中仅有一个马,给定马的当前位置(S)和目标位置(T),求出马最少需要多少跳才能从当前位置到达目标位置。
输入:
本题包含多个测例。输入数据的第一行有一个整数N(1<=N<=1000),表示测例的个数,接下来的每一行有四个以空格分隔的整数,分别表示马当前位置及目标位置的横、纵坐标C(x,y)和G(x,y)。坐标由1开始。
输出:
对于每个测例,在单独的一行内输出一个整数,即马从当前位置跳到目标位置最少的跳数。
输入样例:
21 1 2 11 5 5 1
输出样例:
34
答案如下:
#include<iostream>
#include<queue>using namespace std;int cx,cy,gx,gy;
int a[201][201]={0};
int step[201][201];
//马走的方向所对应的行列变化
int b[8]={-2,-2,-1,-1,1,1,2,2};
int c[8]={-1,1,-2,2,-2,2,-1,1};//结构体内定义队列
struct add
{queue<int>q1;queue<int>q2;
}add;int search(int x,int y);int main()
{int n,i,j,k=0;cin>>n;int ans[n];while(k<n){cin>>cx>>cy>>gx>>gy;//初始化 step[cx][cy]=0;a[cx][cy]=1;add.q1.push(cx);add.q2.push(cy);ans[k++]=search(cx,cy);//清空棋盘和队列,防止下一组测试受到影响 for(i=0;i<201;i++){for(j=0;j<201;j++){a[i][j]=0;step[i][j]=0; }}while(!add.q1.empty()){add.q1.pop();}while(!add.q2.empty()){add.q2.pop();}}for(i=0;i<n;i++){cout<<ans[i]<<endl;} return 0;
}int search(int x,int y)
{int xt,yt,e,f,i;while(1){e=add.q1.front();add.q1.pop();f=add.q2.front();add.q2.pop();for(i=0;i<8;i++){xt=e+b[i];yt=f+c[i];if(xt==gx&&yt==gy){return(step[e][f]+1);}if(xt<1||xt>200||yt<1||yt>200) continue;//剪枝数组越界的情况 if(a[xt][yt]==0){//处理下一组可能的情况 a[xt][yt]=1;step[xt][yt]=step[e][f]+1;add.q1.push(xt);add.q2.push(yt);}}}
}
更多推荐
C++——跳马问题(广搜)
发布评论