本文主要是介绍1043 跳马问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
跳马
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
在国际象棋中，马的走法与中车象棋类似，即俗话说的“马走日”，下图所示即国际象棋中马（K）在一步能到达的格子（其中黑色的格子是能到达的位置）。
现有一200*200大小的国际象棋棋盘，棋盘中仅有一个马，给定马的当前位置（S）和目标位置（T），求出马最少需要多少跳才能从当前位置到达目标位置。
输入：
本题包含多个测例。输入数据的第一行有一个整数N（1<=N<=1000），表示测例的个数，接下来的每一行有四个以空格分隔的整数，分别表示马当前位置及目标位置的横、纵坐标C（x,y）和G（x,y）。坐标由1开始。
输出：
对于每个测例，在单独的一行内输出一个整数，即马从当前位置跳到目标位置最少的跳数。
输入样例：
2 1 1 2 1 1 5 5 1
输出样例：
3 4
#include<iostream>
#include<queue>using namespace std;queue<int>r;
queue<int>c;int nr,nc,ux,uy; //现在的坐标
int ar,ac; //目标坐标
int step[1000],sp[201][201]={0};
int used[201][201]={0};
int dr[8]={-1,-2,-2,-1,1,2,2,1},dc[8]={-2,-1,1,2,2,1,-1,-2}; int search();
int canmoveto(int dire);
void init();
void empty();int main()
{int N,i;cin>>N;for(i=0;i<N;i++){cin>>nr>>nc>>ar>>ac;empty(); init();step[i] = search();}for(i=0;i<N;i++){cout<<step[i]<<endl;}return 0 ;
} void init()
{r.push(nr);c.push(nc);used[nr][nc] = 1;sp[nr][nc] = 0;
}void empty()
{int i,j; while(!r.empty()){r.pop();}while(!c.empty()){c.pop();}for(i = 0;i<201;i++){for(j = 0;j<201;j++){sp[i][j] = 0;used[i][j] = 0;}}
}
int search()
{int i,vx,vy;while(1){ux = r.front();uy = c.front();r.pop();c.pop();for(i=0;i<8;i++){vx = ux + dr[i]; // 移动到当前坐标 vy = uy + dc[i];if(vx == ar && vy == ac) //如果恰好是目标位置 ，返回步数 {return(sp[ux][uy] + 1); }if(canmoveto(i)) //检查是否能移动 {r.push(vx);c.push(vy);used[vx][vy] = 1;sp[vx][vy] = sp[ux][uy] + 1; //步数加一 }}}
}int canmoveto(int dire)
{int tempr,tempc;tempr = ux + dr[dire]; //即将到达的位置 tempc = uy + dc[dire];if(tempr>=1 && tempr<=200 && tempc>=1 && tempc<=200 && used[tempr][tempc]==0) //即将到达的位置不越界 {return 1;}else{return 0;}
}
这篇关于1043 跳马问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
