tags: APCS

d406－倒水時間

題目連結： d406

題目解析

這個問題模擬了水在具有方向性的網格中的流動。水從地圖的頂端某一個位置開始，根據給定的條件，水可以向下、向左、向右流動，而根據不同的情況，水可能也可以向上流動。我們要計算水流到每個位置的最短時間。

解題方向

1. 建立地圖：
   • 使用二維陣列來表示地圖，1 表示有水管（可以通過），0 表示沒有水管（不能通過）。
2. 初始條件：
   • 找到地圖的第一行中最先出現 1 的位置，作為水流開始的位置。
3. 使用 BFS 進行擴展：
   • 使用廣度優先搜尋（BFS）來模擬水的流動，從起始位置開始，依次擴展到相鄰的格子。
   • 在 BFS 中，每個格子都從鄰近的格子中獲得時間標記，這些標記值代表水流到該位置所需的時間。
4. 流動方向控制：
   • 根據輸入的參數 S 來決定水是否可以向上流動。若 S = 1，則允許水往上流動；若 S = 2，則不允許。

程式解析

1. 建立資料結構：
   • MAP：儲存地圖的水管配置。
   • marked：用來標記水流到達每個位置的最短時間，初始值為 0。
2. 尋找起點：
   • 從第一行開始搜尋，找到第一個 1 的位置作為水流的起點，並將其放入 BFS 的佇列 Q 中，並標記該位置的時間為 1。
3. BFS 搜尋：
   • 從佇列中取出當前位置，依次檢查水是否可以流到左、下、右（以及根據 S 決定是否可以向上）的位置。
   • 若可以流動，則將該位置的時間標記為當前時間加一，並將該位置加入佇列中繼續擴展。
4. 輸出結果：
   • 輸出每個地圖的最終標記時間。

完整程式碼

#           (0, -1)
#             [3]
# (-1, 0)[1]  [c]  [2] (1, 0)
#             [0]
#           (0, 1)

#dx = [ 0, 1,  0, -1]
#dy = [ 1, 0, -1,  0]

case=1

while True:
    try:
        #start
        S = int(input())
        N, M = map(int, input().split())

        MAP = []
        for i in range(N):
            row = list(map(int, input().split()))
            MAP.append(row)

        marked = [ [0 for i in range(M)] for j in range(N) ]
        # 全為0的二維陣列

        #====================================================
        r, c = 0, 0

        #find the top row
        # 目的是要找出起點洞口
        while MAP[r][c]==0 :
            c+=1

        # BFS
        Q = [[r, c]]# 起點放入Queue中
        marked[r][c] = 1


        while len(Q) >0:
            now = Q.pop(0)
            r = now[0]
            c = now[1]

            #print(r, c)

            # 左
            if c-1>=0 :
                if MAP[r][c-1] == 1 and marked[r][c-1] ==0:
                    marked[r][c-1] = marked[r][c]+1
                    Q.append([r, c-1])

            # 下
            if r+1<N :
                if MAP[r+1][c] == 1 and marked[r+1][c] ==0:
                    marked[r+1][c] = marked[r][c]+1
                    Q.append([r+1, c])


            # 右
            if c+1<M :
                if MAP[r][c+1] == 1 and marked[r][c+1] ==0:
                    marked[r][c+1] = marked[r][c]+1
                    Q.append([r, c+1])

            # 上
            if r-1>=0 and S==1:
                if MAP[r-1][c] == 1 and marked[r-1][c] == 0:
                    marked[r-1][c] = marked[r][c]+1
                    Q.append([r-1, c])


            #print(Q)
        print("Case %d:" % case)
        for i in range(N):
            for j in range(M):
                print(marked[i][j], end=' ')
            print()

        case+=1

    except:
        break