i793 - pC. WAKUWAKU 尋找興奮源 (⌓‿⌓)

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個安妮亞在一個矩形學園中尋找興奮源的問題。學園由一個二維陣列表示，其中 0 表示可通行，1 表示障礙物，2 表示興奮源。安妮亞從給定的起點開始，每次只能向上下左右移動一格，目標是找到最近的興奮源，並輸出所需的步數。如果無法找到興奮源，則輸出 "WAKUWAKU"。

解題思路

這道題可以使用廣度優先搜尋 (BFS) 演算法來解決。BFS 是一種圖遍歷演算法，可以找到從起點到所有其他節點的最短路徑。

1. 初始化: 建立一個二維陣列 dp，用於記錄每個位置的步數。將所有位置的步數初始化為 -1，表示尚未訪問。
2. 建立佇列: 建立一個佇列 q，用於儲存待訪問的節點。將起點 (x, y) 和初始步數 0 加入佇列。
3. BFS 遍歷:
   • 從佇列中取出一個節點 (tx, ty, stp)，其中 tx 和 ty 是節點的座標，stp 是從起點到該節點的步數。
   • 檢查該節點是否有效：
     • 是否超出學園範圍。
     • 是否為障礙物。
     • 是否已經訪問過。 如果任何一個條件成立，則跳過該節點。
   • 如果該節點是興奮源 (a[tx][ty] == 2)，則輸出 stp 並結束程式。
   • 如果該節點有效且不是興奮源，則將該節點的步數記錄在 dp 陣列中，並將其四個鄰居 (上、下、左、右) 加入佇列，步數加 1。
4. 找不到興奮源: 如果佇列為空，表示無法找到興奮源，則輸出 "WAKUWAKU"。

複雜度分析

• 時間複雜度: O(R * C)，其中 R 是學園的列數，C 是學園的行數。在最壞的情況下，BFS 需要訪問所有節點。
• 空間複雜度: O(R * C)，在最壞的情況下，佇列可能需要儲存所有節點。

程式碼

#include <iostream>
#include <queue>
using namespace std;
int a[1001][1001],dp[1001][1001],n,m,x,y;
queue <pair <int,pair <int,int>>> q;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m >> x >> y;
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j){
			dp[i][j]=-1;
			cin >> a[i][j];
		}
	q.push({0,{x,y}});
	while(!q.empty()){
		int tx=q.front().second.first,ty=q.front().second.second,stp=q.front().first;q.pop();
		if(tx<0||tx>=n||ty<0||ty>=m||a[tx][ty]==1||dp[tx][ty]!=-1)continue;
		if(a[tx][ty]==2){
			cout << stp;
			return 0;
		}
		dp[tx][ty]=stp;
		q.push({stp+1,{tx+1,ty}});
		q.push({stp+1,{tx-1,ty}});
		q.push({stp+1,{tx,ty+1}});
		q.push({stp+1,{tx,ty-1}});
	}
	cout << "WAKUWAKU";
}