魔王迷宮 (APCS 2021-09 中級)

有一個 \(n\times m\) 的棋盤，列編號為 \(0\) 到 \(n-1\)，行編號為 \(0\) 到 \(m-1\)。棋盤上一開始有 \(k\) 隻魔王。

第 \(i\) 隻魔王的起點是 \((r_i,c_i)\)，固定移動向量是 \((s_i,t_i)\)。若它 目前位於 \((x,y)\)，移動後會到達

每一回合都依照以下順序進行：

1. 所有仍在棋盤上的魔王，同時在自己目前所在的格子放下一顆炸彈。
2. 所有仍在棋盤上的魔王，同時依各自的移動向量移動一次。
3. 移動後超出棋盤範圍的魔王立刻消失。
4. 其餘魔王中，凡是移動到已有炸彈的格子，都會引爆該格的炸彈。該格 的所有魔王和所有炸彈同時消失。

第 \(4\) 步是同時判定的。例如，若兩隻魔王在同一回合移動到同一個 有炸彈的格子，兩隻都會消失；不能因為先處理其中一隻並清除炸彈，就讓 另一隻存活。同一格即使有多顆炸彈，答案仍只把這格算作一個有炸彈的 格子。

每隻魔王的四元組 \((r_i,c_i,s_i,t_i)\) 互不相同。遊戲持續進行，直到 棋盤上沒有任何魔王為止。請計算此時還有多少個格子放有至少一顆炸彈。

輸入格式

第一行包含三個整數 \(n,m,k\)。

接下來 \(k\) 行，第 \(i\) 行包含四個整數 \(r_i,c_i,s_i,t_i\)，表示第 \(i\) 隻魔王的起點與固定移動向量。

限制

• \(1\le n,m\le100\)
• \(1\le k\le500\)
• \(0\le r_i<n\)
• \(0\le c_i<m\)
• \(-100\le s_i,t_i\le100\)
• 所有 \((r_i,c_i,s_i,t_i)\) 互不相同。
• 所有輸入都是整數。

輸出格式

輸出一個整數，表示所有魔王消失後，仍放有至少一顆炸彈的格子數。

評分說明

兩筆範例會由評測系統執行，但不計分。另有恰好 \(20\) 個計分測試組， 每組 \(5\) 分：

• 第 \(1\)～\(10\) 組（共 \(50\) 分）：\(n=1\)，且所有魔王皆滿足 \(r_i=0\)、\(s_i=0\)。
• 第 \(11\)～\(20\) 組（共 \(50\) 分）：沒有額外限制。

範例輸入 1

1 6 3
0 0 0 0
0 2 0 -1
0 4 0 2

範例輸出 1

4

範例解釋 1

第一隻魔王第一回合在位置 \(0\) 放下炸彈後沒有移動，因此踩到自己剛放的 炸彈，魔王和該炸彈一起消失。

第二隻魔王依序在位置 \(2,1,0\) 放下炸彈，接著移出棋盤；第三隻魔王在 位置 \(4\) 放下炸彈後便移出棋盤。因此最後位置 \(0,1,2,4\) 共四格有炸彈。

範例輸入 2

5 5 2
0 0 3 2
0 0 2 3

範例輸出 2

3

範例解釋 2

第一回合，兩隻魔王都在 \((0,0)\) 放炸彈，再分別移到 \((3,2)\) 與 \((2,3)\)。第二回合，它們在這兩格放炸彈後都移出棋盤。

最後有炸彈的格子是 \((0,0)\)、\((3,2)\)、\((2,3)\)，共三格。雖然第一回合 在 \((0,0)\) 放了兩顆炸彈，這個位置仍只算一格。

題目來源

APCS 2021 年 9 月實作題第 2 題；規則參考 ZeroJudge g276「魔王迷宮」 與王一哲的題解，題目敘述由 AACPOJ 重新整理並補明回合同步語意與輸入限制。