108年彰雲嘉上午P6 - Knight Moves

2021-09-11

題目：

西洋棋騎士/象棋的馬每步可以沿日字對角走到另一對角，  
現在有一個X*Y的棋盤，左下角座標(0,0)，右下為(X-1,0)  
棋子的起始點為(a,b)，請求出走到(c,d)的最小步數。

其中X,Y<=10000

輸入：

本題有多筆測資，第一行輸入N代表有幾筆測資  
接下來每筆測資有一行，  
依序以空格分開輸入6個正整數X, Y, a, b, c, d

輸出：

針對每筆測資依序輸出最短步數

Ex 1 Input:

2  
10 10 3 4 7 6  
10 10 3 4 9 9

Ex 1 Output:

2  
5

題解：

如果還是不懂騎士走法可參考維基百科

這題是非常經典的最短路問題，可使用BFS(廣度優先搜尋)解。

可以想像有一個確診武漢肺炎的同學坐在班上位置中間，
而病毒就從那位同學開始往旁邊擴散，
每過一天就一個確診，
最後全班都被感染病毒，
然後就能求哪位同學會在第幾天確診。
其原理是利用佇列(<queue>)，造訪所有圖上的位置，
並記錄從起點到每個位置一共走了多少步。

騎士走法是按照日字走的，因此可推論一個點會有八種走法
而步數就是上一個點的步數再+1

上程式碼(當然你可以用struct建立點佇列，就不用宣告那麼多queue跟陣列了)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include<bits/stdc++.h>
using namespace std;
template<class T> long long Mod(T a,T b){return ((a%b)+b)%b;}
#define endl '\n'
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
#define GETOUT cout.tie(0);
#define fr(bob,n,l) for(int bob=(n);bob<(l);++bob)
#define fra(ns,a) for(auto (ns):a)
#define frc(bot,ns,l) for(int bot=(ns);bot<=(l);++bot)
#define frx(i,ns,l) for(int i=(ns);i<(l);++i)
const int MAX=1e9+7;
const int MOD=998244353;
inline int nextint(){
	int x=0,w=1;char ch=0;
  	while(ch<'0'||ch>'9'){
    	if(ch == '-')w=-1;
    	ch=getchar();
  	}
  	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=getchar();
  	return x*w;
}
int movx[8]={-1,2,-2,2,-2,2,-1,1};
int movy[8]={-2,-2,-1,-1,1,1,2,2}; //八種走法
bool visited[10001][10001]; //確認這個點是否走過了
queue<int> bfsx,bfsy;
int dis[10001][10001]; //計算距離
inline void solve(){
	//記得確認上一筆測資是否沒把佇列清乾淨
	while(!bfsx.empty()) bfsx.pop();
	while(!bfsy.empty()) bfsy.pop(); 
	
	
	int X,Y,a,b,c,d;
	cin >> X >> Y >> a >> b >> c >> d;
	// 初始化
	frc(i,0,X){
		frc(j,0,Y){
			dis[i][j]=0;
			visited[i][j]=false;
		}
	}	
	
	int ans=0;
	
	bfsx.push(a);bfsy.push(b);
	visited[a][b]=true;
	//這裡開始BFS
	while((!bfsx.empty())&&(!bfsy.empty())){
		int nowx = bfsx.front();bfsx.pop();
		int nowy = bfsy.front();bfsy.pop();
		if(nowx==c && nowy == d){
			//如果走到目標點了，把所算距離(步數)設為答案
			ans = dis[c][d];
			break;
		}
		for(int k=0;k<8;++k){ //八種走法
			int nextx = nowx+movx[k];
			int nexty = nowy+movy[k];
			if(nextx<0||nextx>=X||nexty<0||nexty>=Y) continue; //不讓棋子走出棋盤
			if(!visited[nextx][nexty]){
				visited[nextx][nexty]=true;
				dis[nextx][nexty] = dis[nowx][nowy]+1;
				bfsx.push(nextx);
				bfsy.push(nexty);
			}
		}
	}
	cout << ans << endl;
}
signed main(){
	IO;
	GETOUT;
	int t;
	cin >> t;
	while(t--)solve();
	return 0;
}