APCS Sep 2021 - g276 Q2 [Python]

Problem statement:

There are k bosses on an n × m board. Boss i starts at (r_i, c_i) and moves by (s_i, t_i) each round, from (x, y) to (x + s_i, y + t_i). Each boss has its own r_i, c_i, s_i, and t_i values. Before moving, every boss places a bomb at its current position. Landing on a bomb triggers an explosion that removes both the boss and the bomb. If two bosses land on the same bomb simultaneously, both explode. Multiple bombs at that position also explode together. A boss that leaves the board disappears. How many cells still contain bombs after all bosses are gone?

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)

---

Solution report:

1. Read input: Read n, m, k, and each boss’s initial position and movement vector.
2. Initialize the board: Create an n x m array the_list filled with 0, indicating no bombs.
3. Simulate each round: Every boss places a bomb at its current position, then all bosses move simultaneously. Remove bosses that leave the board. If a boss lands on a bomb, clear that cell to 0 and remove the boss.
4. Count remaining bombs: Once all bosses are gone, iterate over the_list and total the remaining bombs.

Important points

1. Traverse backward when removing by index:

   • Removing elements from the beginning changes the list length and shifts later indices. For example:

     lst = [1, 2, 3, 4, 5]
     for i in range(len(lst)):
         if lst[i] % 2 == 0:
             lst.pop(i)
     

   After lst[1] is removed, the list becomes [1, 3, 4, 5]. The index keeps increasing, so the next even number, 4, is skipped.

   • Reverse traversal avoids shifting indices of elements that have not yet been visited:

     lst = [1, 2, 3, 4, 5]
     for i in range(len(lst) - 1, -1, -1):
         if lst[i] % 2 == 0:
             lst.pop(i)
     

   Elements after the removed item have already been visited, so they are unaffected.

Key concepts:

• Simulation
• List operations
• Sets

---

• [✔️] You may use the code directly if needed.
• [✔️] Please credit the source when sharing.
• [✔️] Uh… this one was a little slow.

This article was translated from Traditional Chinese by AI. Meaning or wording may differ; please refer to the Traditional Chinese original as the authoritative version.