用布尔矩阵标记被照亮的格子，火把按曼哈顿距离不超过 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;
}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 个格子。时间复杂度是
总结
网格模拟题要先统一坐标，再把“照亮一个格子”的边界判断封装好，后面的标记逻辑会更稳定。