# APCS實作題2021年9月第2題：魔王迷宮

> 日期：2023年9月16日
> 作者：王一哲
> 題目來源：110年9月實作題第2題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=g276)

<br />

## 題目

### 問題描述

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

每個魔王都有不同的 $(r, c, s, t)$ 值，每回合每個魔王移動前會在所在位置上放下一顆炸彈，然後才進行移動，而若魔王移動到已經被放有炸彈的位置，炸彈則會被引爆，該位置的魔王和炸彈則消失不見。如果兩個魔王同時踏到同一個炸彈上會一起被炸掉，如果同一位置上有多個炸彈也會被一起引爆。

當魔王移動超出整個棋盤的範圍，則被視為消失。

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

### 輸入說明

第一行輸入三個正整數 $n (1 \leq n \leq 100)$、$m (1 \leq m \leq 100)$、$k (1 \leq k \leq 500)$，代表盤面大小為 $n \times m$，上面一開始有 $k$ 個魔王。

接下來有 $k$ 行，第 $i$ 行有四個整數 $r_i, c_i, s_i, t_i ~(0 \leq r < n, 0 \leq c < m)$。

配分
- 50分：$n = 1, r_i = 0, s_i = 0$
- 50分：無其它限制
<br />

### 輸出說明

輸出當場上沒有魔王的時候剩下幾格有炸彈
<br />

### 範例一：輸入

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

### 範例一：正確輸出

4

<br />

### 範例二：輸入

5 5 2
0 0 3 2
0 0 2 3

### 範例二：正確輸出

3

<br />

## Python 程式碼

### 版本1，使用二維串列儲存地圖上每一格的炸彈數量，會超時

於 ZeroJudge 測試結果，於第15筆測資會超時。

n, m, k = map(int, input().split())  # 讀取n, m, k
num = k  # 魔王數量
demons = []  # 魔王初位置、移動步數
for _ in range(k):  # 讀取k行的魔王資料
    demons.append(list(map(int, input().split())))

bombs = [[0]*m for _ in range(n)]  # 儲存地圖上炸彈位置的二維串列
outs = [False]*k  # 魔王是否已出局

while num > 0:  # 當還有魔王在場上時繼續執行
    for i in range(k):  # 依序更新每個魔王的狀態
        if not outs[i]: # 如果還沒有出局
            bombs[demons[i][0]][demons[i][1]] += 1  # 於這個位置留下炸彈
            demons[i][0] += demons[i][2]  # 更新x座標
            demons[i][1] += demons[i][3]  # 更新y座標
            if demons[i][0] < 0 or demons[i][0] >= n or demons[i][1] < 0 or demons[i][1] >= m:  # 如果出界，outs 設定為 True，數量減1
                outs[i] = True
                num -= 1
    for x in range(n):  # 檢查每一格地圖
        for y in range(m):
            if bombs[x][y] >= 1:  # 如果格子上有炸彈
                count = 0  # 踩到炸彈的魔王數量
                for i in range(k):  # 檢查還在場上的魔王是否踩到炸彈
                    if demons[i][0] == x and demons[i][1] == y and not outs[i]:
                        outs[i] = True  # 出局
                        num -= 1  # 魔王數量減1
                        count += 1# 踩到炸彈的魔王數量加1
                if count >= 1:  # 如果有魔王踩到炸彈
                    bombs[x][y] = 0  # 將這格的炸彈數量歸0

ans = 0  # 有炸彈的格子數量
for bomb in bombs:  # 讀取地圖上每一個格子，如果格子中有炸彈將 ans 加1
    for b in bomb:
        if b >= 1: ans += 1

print(ans)  # 印出答案

<br /><br />

### 版本2，當魔王出局或炸彈爆炸時移出串列，會超時

於 ZeroJudge 測試結果，於第16筆測資會超時。

n, m, k = map(int, input().split())  # 讀取n, m, k
num = k  # 魔王數量
demons = []  # 魔王初位置、移動步數
for _ in range(k):  # 讀取k行的魔王資料
    demons.append(list(map(int, input().split())))

bombs = []  # 儲存地圖上炸彈位置的二維串列

while demons:  # 當還有魔王在場上時繼續執行
    dc = 0  # 於這一輪出局的魔王數量
    for i in range(len(demons)):  # 依序更新每個魔王的狀態
        idx = i - dc  # 索引值要扣掉出局的魔王數量
        if [demons[idx][0], demons[idx][1]] not in bombs:   # 如果這個位置目前沒有炸彈
            bombs.append([demons[idx][0], demons[idx][1]])  # 於這個位置留下炸彈
        demons[idx][0] += demons[idx][2]  # 更新x座標
        demons[idx][1] += demons[idx][3]  # 更新y座標
        if demons[idx][0] < 0 or demons[idx][0] >= n or demons[idx][1] < 0 or demons[idx][1] >= m:  # 如果出界
            demons.pop(idx)  # 移除這個魔王
            dc += 1  # 出局數加1
    
    bc = 0  # 於這一輪移除的炸彈數量
    for i in range(len(bombs)):  # 檢查每一個炸彈的位置
        count = 0  # 踩到炸彈的魔王數量
        de = 0  # 於這一輪出局的魔王數量
        idx = i - bc  # 索引值要扣掉移除的炸彈數量
        for j in range(len(demons)):  # 檢查還在場上的魔王是否踩到炸彈
            jdx = j - de  # 索引值要扣掉出局的魔王數量
            if demons[jdx][0] == bombs[idx][0] and demons[jdx][1] == bombs[idx][1]:  # 如果踩到炸彈
                demons.pop(jdx)  # 移除這個魔王
                de += 1  # 出局數加1
                count += 1# 踩到炸彈的魔王數量加1
        if count >= 1:  # 如果有魔王踩到炸彈
            bombs.pop(idx)  # 刪除這個炸彈
            bc += 1  # 移除的炸彈數量

print(len(bombs))  # 印出答案

<br /><br />

## C++ 程式碼

用 Python 程式碼版本1改寫成 C++ 程式碼，於 ZeroJudge 測試結果，最長運算時間約為 10 ms，使用記憶體最多約為 360 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    int n, m, k; cin >> n >> m >> k;  // 讀取n, m, k
    int num = k;  // 魔王數量
    int demons[k][4], bombs[n][m];  // 魔王初位置、移動步數，儲存地圖上炸彈位置
    bool outs[k] = {false};  // 魔王是否已出局
    /* 讀取k行的魔王資料 */
    for(int i=0; i<k; i++) {
        for(int j=0; j<4; j++) { 
            cin >> demons[i][j];
        }
    }
    /* 地圖上每個格子的炸彈數量 */
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            bombs[i][j] = 0;
        }
    }

    /* 當還有魔王在場上時繼續執行 */
    while(num > 0) {
        for(int i=0; i<k; i++) {  // 依序更新每個魔王的狀態
            if (!outs[i]) {  // 如果還沒有出局
                bombs[demons[i][0]][demons[i][1]]++;  // 於這個位置留下炸彈
                demons[i][0] += demons[i][2];  // 更新x座標
                demons[i][1] += demons[i][3];  // 更新y座標
                if (demons[i][0] < 0 || demons[i][0] >= n || demons[i][1] < 0 || demons[i][1] >= m) {  // 如果出界，outs 設定為 True，數量減1
                    outs[i] = true;
                    num--;
                }
            }
        }
        for(int x=0; x<n; x++) {  // 檢查每一格地圖
            for(int y=0; y<m; y++) {
                if (bombs[x][y] >= 1) {  // 如果格子上有炸彈
                    int count = 0;  // 踩到炸彈的魔王數量
                    for(int i=0; i<k; i++) {  // 檢查還在場上的魔王是否踩到炸彈
                        if (demons[i][0] == x && demons[i][1] == y && !outs[i]) {
                            outs[i] = true;  // 出局
                            num--;  // 魔王數量減1
                            count++;// 踩到炸彈的魔王數量加1
                        }
                    }
                    if (count >= 1) bombs[x][y] = 0;  // 如果有魔王踩到炸彈，將這格的炸彈數量歸0
                }
            }
        }
    }
    
    /* 計算答案 */
    int ans = 0;  // 有炸彈的格子數量
    for(int i=0; i<n; i++) {  // 讀取地圖上每一個格子，如果格子中有炸彈將 ans 加1
        for(int j=0; j<m; j++) {
            if (bombs[i][j] >= 1) ans++;
        }
    }
    cout << ans << endl;  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`