魔王迷宮

解題想法

1. 設立二維陣列

題目敘述中提到， $n, m, k$ 可以用來代表一個大小為 $n \times m$ 的二維陣列，和五個長度為 $k$ 的一維陣列。因此，我們可以建立這些陣列來記錄：

bool bomb[n][m] : 記錄 $(n, m)$ 是否有炸彈。
bool explode[n][m] : 記錄 $(n, m)$ 是否爆炸。
int r[k], c[k] : 第 $k$ 位魔王的起始位置 $(r, c)$ 。
int s[k], t[k] : 第 $k$ 位魔王每回合垂直移動 $s$ ，平行移動 $t$ 。

以上六個陣列將會在解題過程中持續使用。

2. 魔王放置炸彈

每回合一開始時，每位魔王都要在自己位置上放炸彈，即 r[] 和 c[] 。因此我們可以將狀態存入 bomb[][] 中，代表此地有炸彈：

for (int i = 0; i < k; i++) {
    bomb[r[i]][c[i]]++;
}

3. 魔王移動

魔王放完炸彈後，每位魔王會依自己的移動方式移動。因此我們可以將其原位置 r[] 和 c[] ，各自加上 s[] 和 t[] ，從而更新其位置：

for (int i = 0; i < k; i++) {
    bomb[r[i]][c[i]]++;
    r[i] += s[i];
    c[i] += t[i];
}

4. 魔王刪除

題目敘述中，有給予兩個魔王死亡的條件：

魔王出界。
魔王碰到炸彈並炸死。

因此，我們可以做出以下兩個判斷式。

1. 出界檢測

當魔王位置超出 $[0, n)$ 和 $[0, m)$ 時，以下判斷式可以將魔王移出：

for (int i = 0; i < k; i++) {
	if (r[i] < 0 || r[i] >= n || c[i] < 0 || c[i] >= m) {
	    r[i] = c[i] = -100;
	    lef--; //魔王剩餘數量
	}
	...
}

2. 炸彈檢測

當魔王碰到炸彈時，以下判斷式可以將此位置的 explode[] 設為 true ，之後來到這位置魔王都會被移出，同時將此位置的 bomb[] 設定為 false ：

for (int i = 0; i < k; i++) {
	...
	if (bomb[i]) {
	    r[i] = c[i] = -100;
	    lef--; //魔王剩餘數量
	}
}

5. 清除炸彈

每次回合結束後，會將 explode[] 的所有值設定為 false ，避免影響到之後的回合：

memset(explode, 0, sizeof(explode));

範例程式

#include <bits/stdc++.h>
using namespace std;

int n, m, k, lef = 0, r[505], c[505], s[505], t[505], bomb[105][105], ans = 0;
bool explode[105][105];

int main() {
    memset(bomb, 0, sizeof(bomb));
    memset(explode, 0, sizeof(explode));
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) cin >> r[i] >> c[i] >> s[i] >> t[i];
    lef = k;
    do {
        for (int i = 0; i < k; i++) {
            if (r[i] == -100 && c[i] == -100) continue;
            bomb[r[i]][c[i]]++;
            r[i] += s[i];
            c[i] += t[i];
        }
        for (int i = 0; i < k; i++) {
            if (r[i] == -100 && c[i] == -100) continue;
            if (r[i] < 0 || r[i] >= n || c[i] < 0 || c[i] >= m) {
                r[i] = c[i] = -100;
                lef--;
            }
            else if (bomb[r[i]][c[i]] || explode[r[i]][c[i]]) {
                bomb[r[i]][c[i]] = 0, explode[r[i]][c[i]] = 1;
                r[i] = c[i] = -100;
                lef--;
            }
        }
        memset(explode, 0, sizeof(explode));
    } while (lef);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (bomb[i][j]) ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}