【Mc生存】插火把
用布尔矩阵标记被照亮的格子，火把按曼哈顿距离不超过 2 标记，萤石标记 5x5 方块。
OJ: luogu
题目 ID: P1789
难度:入门
标签:模拟矩阵python
日期: 2026-07-15 18:58
题意
在 n * n 方阵中放火把和萤石。被光照到的位置不会生成怪物，问最后有多少格没有被照亮。
火把照亮的是以它为中心、曼哈顿距离不超过 2 的格子；萤石照亮的是以它为中心的 5 * 5 方块。
思路
用二维布尔列表 lit 记录每个格子是否被照亮。
为了处理边界，写一个小函数 light_cell(row, col)：只有坐标在棋盘内时才标记为亮。
火把枚举 dx, dy 从 -2 到 2，只标记满足：
text
abs(dx) + abs(dy) <= 2的位置。萤石则直接标记整个 5 * 5 范围。
最后扫描整个矩阵，统计仍然为 False 的格子。
这题是网格模拟，正解就是直接标记，不创建 brute.py。
Python 知识
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：二维矩阵用列表推导式创建。/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：嵌套range循环适合枚举二维偏移。- 坐标输入从
1开始，代码中减一转成 Python 的0下标。 abs(dx) + abs(dy)是曼哈顿距离。
代码
python
n, torch_count, glowstone_count = map(int, input().split())
lit = [[False for _ in range(n)] for _ in range(n)]
def light_cell(row, col):
if 0 <= row < n and 0 <= col < n:
lit[row][col] = True
for _ in range(torch_count):
x, y = map(int, input().split())
x -= 1
y -= 1
for dx in range(-2, 3):
for dy in range(-2, 3):
if abs(dx) + abs(dy) <= 2:
light_cell(x + dx, y + dy)
for _ in range(glowstone_count):
x, y = map(int, input().split())
x -= 1
y -= 1
for dx in range(-2, 3):
for dy in range(-2, 3):
light_cell(x + dx, y + dy)
answer = 0
for row in range(n):
for col in range(n):
if not lit[row][col]:
answer += 1
print(answer)cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-27 00:00
* update_at: 2026-07-27 00:00
*/
#include <bits/stdc++.h>
using namespace std;
bool lit[105][105]; // 是否被照亮
int n, t, g; // 棋盘大小、火把数、萤石数
int main() {
cin >> n >> t >> g;
int x, y;
// 处理火把：曼哈顿距离 <= 2
for (int k = 1; k <= t; k++) {
cin >> x >> y;
for (int dx = -2; dx <= 2; dx++)
for (int dy = -2; dy <= 2; dy++)
if (abs(dx) + abs(dy) <= 2) { // 曼哈顿距离条件
int nx = x + dx, ny = y + dy;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
lit[nx][ny] = true;
}
}
// 处理萤石：5x5 正方形
for (int k = 1; k <= g; k++) {
cin >> x >> y;
for (int dx = -2; dx <= 2; dx++)
for (int dy = -2; dy <= 2; dy++) {
int nx = x + dx, ny = y + dy;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
lit[nx][ny] = true;
}
}
// 统计未被照亮的格子
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (!lit[i][j]) ans++;
cout << ans;
return 0;
}Guide 风格代码
cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-14 14:54
* update_at: 2026-08-14 14:54
*/
/* P1789 Mc生存：模拟火把与萤石的照亮范围，统计未被照亮的格子。 */
#include <iostream>
#include <cmath>
const int max_n = 105; // n 最大为 100
bool lit[max_n][max_n]; // lit[row][col] = true 表示 (row, col) 被照亮
int n, torch_count, glowstone_count;
int main() {
std::cin >> n >> torch_count >> glowstone_count;
// 火把：照亮曼哈顿距离不超过 2 的格子。
for (int k = 0; k < torch_count; k += 1) {
int x, y;
std::cin >> x >> y;
x -= 1; // 输入是 1 起始坐标，转成 0 起始下标
y -= 1;
for (int dx = -2; dx <= 2; dx += 1) {
for (int dy = -2; dy <= 2; dy += 1) {
if (std::abs(dx) + std::abs(dy) > 2) {
continue; // 超出火把范围的角落格子
}
int nx = x + dx;
int ny = y + dy;
if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
continue; // 越界
}
lit[nx][ny] = true;
}
}
}
// 萤石：照亮以自己为中心的 5x5 正方形。
for (int k = 0; k < glowstone_count; k += 1) {
int x, y;
std::cin >> x >> y;
x -= 1;
y -= 1;
for (int dx = -2; dx <= 2; dx += 1) {
for (int dy = -2; dy <= 2; dy += 1) {
int nx = x + dx;
int ny = y + dy;
if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
continue; // 越界
}
lit[nx][ny] = true;
}
}
}
int dark_count = 0; // 没被照亮、会生成怪物的格子数
for (int row = 0; row < n; row += 1) {
for (int col = 0; col < n; col += 1) {
if (!lit[row][col]) {
dark_count += 1;
}
}
}
std::cout << dark_count << '\n';
return 0;
}Pythonic 写法
用 product 生成偏移，集合并入照亮坐标，答案为 n*n - len(lit)：
python
from itertools import product
n, torch_count, glowstone_count = map(int, input().split())
lit = set()
for _ in range(torch_count):
x, y = map(int, input().split())
lit |= {
(x + dx, y + dy)
for dx, dy in product(range(-2, 3), repeat=2)
if abs(dx) + abs(dy) <= 2 and 1 <= x + dx <= n and 1 <= y + dy <= n
}
for _ in range(glowstone_count):
x, y = map(int, input().split())
lit |= {
(x + dx, y + dy)
for dx, dy in product(range(-2, 3), repeat=2)
if 1 <= x + dx <= n and 1 <= y + dy <= n
}
print(n * n - len(lit))复杂度
每个光源最多标记 25 个位置，最后扫描 n^2 个格子。时间复杂度是
总结
网格模拟题要先统一坐标，再把“照亮一个格子”的边界判断封装好，后面的标记逻辑会更稳定。