d191 - 11352 - Crazy King
題目描述
題目描述了彼得王需要從 A 王國走到 B 王國，中間隔著一個有敵人的森林。森林可以看作一個棋盤，敵人可以像西洋棋的馬一樣移動。彼得王可以像西洋棋的國王一樣移動。要求找到從 A 到 B 的最短路徑，如果無法到達則輸出特定訊息。
解題思路
這題可以將棋盤看作一個圖，A 是起點，B 是終點。棋盤上的每個空格都是一個節點。國王可以移動到相鄰的八個格子（像西洋棋的國王），但如果相鄰的格子有敵人或敵人可以一步跳到該格子，則不能移動。可以使用廣度優先搜尋 (BFS) 來找到從 A 到 B 的最短路徑。
程式碼中，mp 陣列儲存棋盤的狀態，p 陣列用於標記被敵人影響的格子。zfs 函數用於標記所有被馬可以到達的格子。dfs 函數實際上是 BFS 的實現，它從 A 開始搜尋，並更新到 B 的最短距離。如果找不到路徑，則 ans 保持初始值，輸出 "King Peter, you can't go now!"，否則輸出最短路徑長度。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 是棋盤的列數，m 是棋盤的行數。因為 BFS 最多會訪問每個格子一次。
- 空間複雜度: O(n*m)，主要用於儲存
dp陣列和p陣列，以及 BFS 的佇列（在最壞情況下，佇列可能包含所有格子）。
程式碼
#include <iostream>
using namespace std;
int t,n,m,sn,sm,ans,dp[105][105];
char mp[105][105],p[105][105];
bool judge(int x,int y){
if(x>=n||y>=m||x<0||y<0||mp[x][y]=='A'||mp[x][y]=='B')return 0;
return 1;
}
void zfs(int x,int y){
for(int i=1;i<=2;++i){
for(int j=1;j<=2;++j){
if(i+j==3){
if(judge(x+i,y+j)){
p[x+i][y+j]='Z';
}
if(judge(x-i,y+j)){
p[x-i][y+j]='Z';
}
if(judge(x+i,y-j)){
p[x+i][y-j]='Z';
}
if(judge(x-i,y-j)){
p[x-i][y-j]='Z';
}
}
}
}
}
void dfs(int x,int y,int s){
if(x<0||y<0||x>=n||y>=m||s>=ans||s>=dp[x][y]||p[x][y]=='Z')return;
dp[x][y]=min(s,dp[x][y]);
if(p[x][y]=='B'){
ans=min(s,ans);
return;
}
for(int i=-1;i<=1;++i)
for(int j=-1;j<=1;++j)
if(i||j)dfs(x+i,y+j,s+1);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n >> m;
ans=n*m+1;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
dp[i][j]=ans;
cin >> mp[i][j];
p[i][j]=mp[i][j];
if(p[i][j]=='A'){
sn=i;
sm=j;
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(mp[i][j]=='Z'){
zfs(i,j);
}
}
}
dfs(sn,sm,0);
if(ans==n*m+1){
cout << "King Peter, you can't go now!\n";
}
else{
cout << "Minimal possible length of a trip is " << ans << '\n';
}
}
}