解題想法#
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;
}
