f699 - 品嘉的茶葉蛋
題目描述
題目描述了一個 N x M 的地圖，其中包含可通行路徑 (0)、茶葉蛋 (1) 和障礙物 (2)。品嘉從 (0, 0) 出發，需要計算到達每個茶葉蛋所需的步數，並按照步數從小到大輸出。如果無法到達任何茶葉蛋，則輸出 "嘉油！"。
解題思路
本題可以使用廣度優先搜尋 (BFS) 演算法來解決。從起點 (0, 0) 開始，將所有可到達的格子進行遍歷，並記錄到達每個格子的步數。對於每個茶葉蛋，如果可以從起點到達，則將其步數存儲起來。最後，將所有茶葉蛋的步數進行排序，並按照排序後的順序輸出。如果沒有茶葉蛋可以到達，則輸出 "嘉油！"。
複雜度分析
- 時間複雜度: O(N * M)
- 空間複雜度: O(N * M)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int a[101][101],b[101][101],n,m,ans[101],it;
inline void bfs(int x,int y,int step){
if(x>=n||y>=m||x<0||y<0||a[x][y]==2||step>=b[x][y])return;
b[x][y]=step;
bfs(x+1,y,step+1);
bfs(x-1,y,step+1);
bfs(x,y+1,step+1);
bfs(x,y-1,step+1);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j){
cin >> a[i][j];
b[i][j]=999;
}
bfs(0,0,0);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(a[i][j]==1&&b[i][j]!=999){
ans[it]=b[i][j];
++it;
}
if(it==0)
cout << "嘉油！";
else{
sort(ans,ans+it);
for(int i=0;i<it;++i)
cout << ans[i] << "\n";
}
}