d406 - 倒水時間
題目描述
題目描述了一個水管網路，水從頂部開始流動，需要計算每個位置被水覆蓋的時間。水可以向下、向左、向右流動，取決於輸入的模式 (mode)。如果 mode 為 1，水還可以向上流動。如果某個位置無法到達，則輸出 0。
解題思路
本題可以使用廣度優先搜尋 (BFS) 來解決。將地圖視為一個圖，每個有水管的位置都是一個節點。水從頂部開始流動，可以看作從頂部水管的節點開始進行 BFS。在 BFS 的過程中，記錄每個節點被訪問的時間。
具體來說，程式碼中定義了兩個 BFS 函數 bfs1 和 bfs2，分別對應 mode 為 1 和 2 的情況。bfs1 允許水向上流動，而 bfs2 不允許。在 BFS 的過程中，檢查相鄰節點是否在圖的範圍內、是否有水管以及是否已經被訪問過。如果滿足這些條件，則更新相鄰節點的訪問時間，並將其加入佇列中。
程式碼首先讀取輸入，包括模式、地圖大小和地圖本身。然後，從地圖的頂部找到一個有水管的位置，作為 BFS 的起點。執行 BFS，計算每個位置被水覆蓋的時間。最後，輸出結果。
複雜度分析
- 時間複雜度: O(N * M)，其中 N 是地圖的行數，M 是地圖的列數。因為 BFS 最多會訪問每個節點一次。
- 空間複雜度: O(N * M)，因為
water陣列和佇列在最壞情況下可能需要儲存所有節點的資訊。