洛谷：P1789：插火把

题目

P1789：插火把

分析

本题的核心是搞清楚“火把”和“萤石”的照明范围。

火把照明范围分析

一个火把最多影响5行5列。其中：

1. -2/+2行，只影响正上/下方（最多）1格
2. -1/+1行，影响左上、正上、右上（最多）3格
3. 本行，影响左2到右2（最多）5格

同时，需要判断越界的可能。

萤石照明范围分析

一个萤石最多影响5行5列，而且是一个以萤石位置(x, y)为中心的正方形。也要判断越界的可能。

最后，再次双重循环统计“黑暗”区域的数量即可。

答案

思考

这里，可以引进“曼哈顿距离”。火炬的照明范围正好是两点之间曼哈顿距离小于等于2的点。¹而且，这么做之后，其越界判定就可以和萤石的判定一致。有兴趣的读者可以自行完成。

        for (int dx = -2; dx <= 2; dx++)
        {
            for (int dy = -2; dy <= 2; dy++)
            {
                // 曼哈顿距离 <= 2（十字形）
                if (abs(dx) + abs(dy) <= 2)
                {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
                    {
                        grid[nx][ny] = true;
                    }
                }
            }
        }