Mc生存-插火把

洛谷·深入浅出 · 代码 · cpp · 难度 4/5 · 共 1322 字

标记火把/萤石光照范围，统计未照亮（生怪）点数

洛谷
练习

正文

// 原题：https://oj.yecheng.tv/p/1410
// 题意：n×n 方格中放置 m 个火把、k 个萤石，火把/萤石照亮曼哈顿距离<=2 的区域；求未被照亮（生怪物）的格子数。
// 思路：标记所有被照亮格；坐标 1 起转 0 起；枚举其曼哈顿半径 2 范围标记；统计暗格。
// 复杂度：O((m+k)*n^2)。
// 易错点：坐标 1 起需减 1；照亮为曼哈顿距离<=2 的菱形；未照亮格才算怪物。
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int lit[110][110];
int main(){
    string line;
    if(!getline(cin, line)) return 0;
    int n, m, k;
    istringstream iss(line);
    iss >> n >> m >> k;
    for(int i = 0; i < m; i++){
        int x, y; cin >> x >> y; 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 >= 0 && nx < n && ny >= 0 && ny < n) lit[nx][ny] = 1;
                }
    }
    for(int i = 0; i < k; i++){
        int x, y; cin >> x >> y; 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 >= 0 && nx < n && ny >= 0 && ny < n) lit[nx][ny] = 1;
                }
    }
    int dark = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(!lit[i][j]) dark++;
    cout << dark << endl;
    return 0;
}

Mc生存-插火把

正文

洛谷·深入浅出的其它内容