【題目描述】

輸入n代表有個(gè)n×n的棋盤(pán)，輸入開(kāi)始位置的坐標(biāo)和結(jié)束位置的坐標(biāo)，問(wèn)一個(gè)騎士朝棋盤(pán)的八個(gè)方向走馬字步，從開(kāi)始坐標(biāo)到結(jié)束坐標(biāo)可以經(jīng)過(guò)多少步。

【輸入】

首先輸入一個(gè)n,表示測(cè)試樣例的個(gè)數(shù)。

每個(gè)測(cè)試樣例有三行。

第一行是棋盤(pán)的大小L(4≤L≤300)；

第二行和第三行分別表示馬的起始位置和目標(biāo)位置(0..L?1)。

【輸出】

馬移動(dòng)的最小步數(shù)，起始位置和目標(biāo)位置相同時(shí)輸出0。

【輸入樣例】

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

【輸出樣例】

5
28
0

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 310 #define MOD 2520 #define E 1e-12 using namespace std; int n; char a[N][N]; bool vis[N][N]; int dir[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}}; struct node {int x;int y;int step; }q[100000]; void bfs(int sx,int sy,int ex,int ey) {int head=1,tail=1;memset(vis,0,sizeof(vis));vis[sx][sy]=1;q[tail].x=sx;q[tail].y=sy;q[tail].step=0;tail++;while(head<tail){int x=q[head].x;int y=q[head].y;int step=q[head].step;if(x==ex&&y==ey){printf("%d\n",step);break;}for(int i=0;i<8;i++){int nx=x+dir[i][0];int ny=y+dir[i][1];if(nx>=0&&nx<n&&ny>=0&&ny<n&&vis[nx][ny]==0){vis[nx][ny]=1;q[tail].x=nx;q[tail].y=ny;q[tail].step=step+1;tail++;}}head++;} } int main() {int t;int sx,sy,ex,ey;scanf("%d",&t);while(t--){scanf("%d",&n);scanf("%d%d%d%d",&sx,&sy,&ex,&ey);bfs(sx,sy,ex,ey);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Knight Moves（信息学奥赛一本通-T1257）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。