# **APCS Sep 2021 - g276 [Q2](https://zerojudge.tw/ShowProblem?problemid=g276) [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)

---

**解題報告：**

題目動作說明：

1. **輸入數據**：
- 讀取 `n`, `m`, `k`，以及每個魔王的初始位置和移動向量。

2. **初始化棋盤**：
- 創建一個大小為 `n x m` 的棋盤 `the_list`，初始值為 0，表示沒有炸彈。

3. **模擬每回合魔王的行為**：
- 每回合每個魔王在當前位置放置一顆炸彈。
- 所有魔王移動到下一個位置(同時)。
- 如果移動到邊界外，魔王消失。
- 如果移動到已有炸彈的位置，炸彈引爆(此區炸彈為0)，並移除該魔王。

4. **計算剩餘炸彈數量**：
- 當所有魔王都消失後，迴圈 `the_list` 並計算所有剩餘炸彈的數量。

### 本題重點：

1. **第一個 `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)

這樣，每次刪除元素時，後面的元素已經被迴圈，不會受到影響。

**本題知識：**
* **模擬**
* **列表操作**
* **集合**

---

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