APCS Sep 2021 - g276

APCS Sep 2021 - g276 Q2 [Python]

本題敘述：

在一個 n x m 的棋盤上有 k 個魔王，一開始第 i 個魔王位於 (r_i, c_i) 的位置上，並且每回合會移動 (s_i, t_i)。也就是說，若本來在 (x, y) 位置，經過移動後會跳到 (x + s_i, y + t_i) 位置。

每個魔王都有不同的 r_i, c_i, s_i, t_i 值，每回合每個魔王移動前會在位置放下一顆炸彈，然後才進行移動，而若魔王移動到炸彈的位置，炸彈則會引爆。魔王移動和炸彈消失不見。如果兩個魔王同時踏到同一個炸彈上會一起引爆。如果同一位置有多個炸彈也會被一起引爆。當魔王移動超出整個棋盤的範圍，則視為消失。

請計算，當棋盤上沒有任何魔王時，盤面上總共剩下幾格有炸彈？

n, m, k = map(int, input().split())

the_list = [[0 for _ in range(m)] for _ in range(n)]

boss = []

for _ in range(k):
    r, c, s, t = map(int, input().split())
    boss.append([r, c, s, t])

while boss:
    boom = set()
    to_remove = []

    for i in range(len(boss)):
        r, c = boss[i][0], boss[i][1]
        if the_list[r][c] == 0:  # 只有位置為0才要增加
            the_list[r][c] = 1

    for i in range(len(boss) - 1, -1, -1):  # range(起始值, 結束值(不會碰到), 增量) 
        r, c, s, t = boss[i]
        new_r, new_c = r + s, c + t
        
        if new_r >= n or new_c >= m or new_r < 0 or new_c < 0:  # 確認是否超出邊界
            to_remove.append(i)
            continue

        if the_list[new_r][new_c] > 0:
            if (new_r, new_c) not in boom:
                boom.add((new_r, new_c))
            to_remove.append(i)
        else:
            boss[i][0], boss[i][1] = new_r, new_c

    for i in sorted(to_remove, reverse=True): # 確保不會影響要移除的boss順序
        boss.pop(i)
    
    for (r, c) in boom:
        the_list[r][c] = 0

# 計算剩餘的炸彈數量
total = 0
for row in the_list:
    total += sum(row)

print(total)

解題報告：

題目動作說明：

輸入數據：
- 讀取 n, m, k，以及每個魔王的初始位置和移動向量。
初始化棋盤：
- 創建一個大小為 n x m 的棋盤 the_list，初始值為 0，表示沒有炸彈。
模擬每回合魔王的行為：
- 每回合每個魔王在當前位置放置一顆炸彈。
- 所有魔王移動到下一個位置(同時)。
- 如果移動到邊界外，魔王消失。
- 如果移動到已有炸彈的位置，炸彈引爆(此區炸彈為0)，並移除該魔王。
計算剩餘炸彈數量：
- 當所有魔王都消失後，迴圈 the_list 並計算所有剩餘炸彈的數量。

本題重點：

第一個 for 迴圈要用倒序：
- 當你在列表中要使用i刪除元素時，如果從頭到尾按正序迴圈並刪除元素，會導致列表長度變化，影響後續元素的索引。例如：
```
lst = [1, 2, 3, 4, 5]
for i in range(len(lst)):
    if lst[i] % 2 == 0:
        lst.pop(i)
```
  在第一次迴圈中，lst[1] 被刪除，此時列表變為 [1, 3, 4, 5]，但是索引 i 會繼續增加，導致下一個偶數 4 被跳過。
- 而倒序迴圈確保當刪除元素時，不會影響尚未迴圈的元素的索引。例如：
```
lst = [1, 2, 3, 4, 5]
for i in range(len(lst) - 1, -1, -1):
    if lst[i] % 2 == 0:
        lst.pop(i)
```
  這樣，每次刪除元素時，後面的元素已經被迴圈，不會受到影響。

本題知識：

模擬
列表操作
集合

[✔️] 程式碼如果需要可以直接使用。
[✔️] 分享貼文請標註來源。
[✔️] 呃呃...這次有點慢。