【Mc 生存】插火把

题目链接

题目描述

话说有一天 linyorson 在“我的世界”开了一个 $n \times n$ 的方阵，现在他有 $m$ 个火把和 $k$ 个萤石，分别放在 $(x_1, y_1) \sim (x_m, y_m)$ 和 $(o_1, p_1) \sim (o_k, p_k)$ 的位置，没有光并且没放东西的地方会生成怪物。请问在这个方阵中有几个点会生成怪物？

P.S. 火把的照亮范围是：

1
2
3
4
5
|暗|暗| 光 |暗|暗|
|暗|光| 光 |光|暗|
|光|光|火把|光|光|
|暗|光| 光 |光|暗|
|暗|暗| 光 |暗|暗|

萤石：

1
2
3
4
5
|光|光| 光 |光|光|
|光|光| 光 |光|光|
|光|光|萤石|光|光|
|光|光| 光 |光|光|
|光|光| 光 |光|光|

输入格式

输入共 $m + k + 1$ 行。
第一行为 $n, m, k$。
第 $2$ 到第 $m + 1$ 行分别是火把的位置 $x_i, y_i$。
第 $m + 2$ 到第 $m + k + 1$ 行分别是萤石的位置 $o_i, p_i$。

注：可能没有萤石，但一定有火把。

输出格式

有几个点会生出怪物。

样例 #1

样例输入 #1

1
2
5 1 0
3 3

样例输出 #1

1
12

提示

数据保证，$1 \le n \le 100$，$1 \leq m+k \leq 25$，$1 \leq m \leq 25$，$0 \leq k \leq 5$。

题解

1. 第一次尝试

非常简单的模拟，只需要开一个 mcMap[][] 二维数组，记录哪里有火把哪里有石头就可以了。遍历一遍有火把或者石头就更新光亮。有光亮的就直接跳过。

1
2
3
4
5
6
7
8
9
10
11
12
// fire 2, stone 3, light 1
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= n; j++)
    {
        if(McMap[i][j] == 1) continue;
        if (McMap[i][j] == 2)
            fireLight(i, j);
        else if (McMap[i][j] == 3)
            stoneLight(i, j);
    }
}

只有四十分。。。
很显然因为只有一个数组，在更新的时候会覆盖火把或者石头

2. 第二次尝试

既然只需要不被光亮覆盖，再开一个 flag[][]单独存储火把和石头的位置就可以了。

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if(McMap[i][j] == 1) continue;
            if (flag[i][j] == 2)
                fireLight(i, j);
            else if (flag[i][j] == 3)
                stoneLight(i, j);
        }
    }

还是只有四十分。。。
怎么回事！下载了错误的测试样例后发现了问题还是出在上面的二重循环中，本想着在有光亮的的地方就直接跳过剪枝了，没想到直接剪到大动脉上了，if(McMap[i][j] == 1) continue; ，因为火把或石头的位置可能被其他地方的光源照亮，如果直接跳过这个位置就会跳过更新光亮的 flag 判断语句，造成光亮更新失误。

3. 最后一次提交

只需要删除那句话即可。
最后代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int mcMap[115][115];
int flag[115][115];
void fireLight(int x, int y)
{
    mcMap[x][y] = 1;
    mcMap[max(1, x - 1)][y] = 1;
    mcMap[max(1, x - 2)][y] = 1;
    mcMap[max(1, x - 1)][max(1, y - 1)] = 1;
    mcMap[x][max(1, y - 1)] = 1;
    mcMap[x][max(1, y - 2)] = 1;
    mcMap[min(n, x + 1)][y] = 1;
    mcMap[min(n, x + 2)][y] = 1;
    mcMap[min(n, x + 1)][max(1, y - 1)] = 1;
    mcMap[x][min(n, y + 1)] = 1;
    mcMap[x][min(n, y + 2)] = 1;
    mcMap[max(1, x - 1)][min(n, y + 1)] = 1;
    mcMap[min(n, x + 1)][min(n, y + 1)] = 1;
}

void stoneLight(int x, int y)
{
    mcMap[x][y] = 1;
    for (int i = max(1, x - 2); i <= min(n, x + 2); i++)
    {
        for (int j = max(1, y - 2); j <= min(n, y + 2); j++)
        {
            mcMap[i][j] = 1;
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    // fire 2, stone 3, light 1
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        flag[x][y] = 2;
    }
    for (int i = 1; i <= k; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        flag[x][y] = 3;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (flag[i][j] == 2)
                fireLight(i, j);
            else if (flag[i][j] == 3)
                stoneLight(i, j);
        }
    }
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (!mcMap[i][j])
                sum++;
        }
    }
    printf("%d\n", sum);
    return 0;
}

后记

能 AC 的代码就是好代码。可以明显地看到我那个丑陋地 fireLight 函数，十二个位置直接暴力更新，实际上这是很容易犯错误地写法，如果写错了然后去找错误将是极大地麻烦。在 Github Copilot 地带领下很幸运我一次性写对了。正确地比较稳妥地方式是开dx[]和dy[]数组，将所有坐标一次性写出来，然后 for 循环去更新。

1
2
int dx1[13]={2,0,-2,0,1,1,1,0,0,0,-1,-1,-1},
    dy1[13]={0,2,0,-2,0,1,-1,1,0,-1,0,1,-1};

对于数组越界问题解决方案：

  1. 像我一样用 min，max 判断
  2. 直接把(3,3)当原点避免数组下标为负数
  3. 自定义函数判断是负数就返回零