传送门:http://ybt.ssoier.cn:8088/problem_show.php?pid=1257
【题目描述】
输入n
代表有个n×n
的棋盘,输入开始位置的坐标和结束位置的坐标,问一个骑士朝棋盘的八个方向走马字步,从开始坐标到结束坐标可以经过多少步。
【输入】
首先输入一个n
,表示测试样例的个数。
每个测试样例有三行。
第一行是棋盘的大小L(4≤L≤300)
;
第二行和第三行分别表示马的起始位置和目标位置(0..L−1)
。
【输出】
马移动的最小步数,起始位置和目标位置相同时输出0
。
【输入样例】
3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1
【输出样例】
5 28 0
#include<iostream> #include<queue> #include<cstring> using namespace std; #define N 300+1 struct node{ int x,y,t; }; int sx,sy,ex,ey,l,t; int xs[]={1,1,-1,-1,2,2,-2,-2}; int ys[]={2,-2,2,-2,1,-1,1,-1}; bool maps[N][N]; void bfs() { queue<node>q; node st; st.x=sx; st.y=sy; st.t=0; q.push(st); while(!q.empty()) { node nt=q.front();q.pop(); if(nt.x==ex&&nt.y==ey) { cout<<nt.t<<endl; break; } for(int i=0;i<8;i++) { int x=nt.x+xs[i]; int y=nt.y+ys[i]; if(maps[x][y]==true&&x>=0&&x<l&&y>=0&&y<l) { maps[x][y]=false; node tmp; tmp.x=x; tmp.y=y; tmp.t=nt.t+1; q.push(tmp); } } } return ; } int main() { cin>>t; while(t--) { memset(maps,true,sizeof(maps)); cin>>l; cin>>sx>>sy>>ex>>ey; maps[sx][sy]=false; bfs(); } }