E. 着火的森林¶

分数：150分

两位至尊大战至宇宙边荒，大道都磨灭了...

但是种子依然会发芽，不是吗？

【提醒：附件 Tab 中有数据生成器与 开始框架】

更新¶

目前版本的评测机可用如下的代码输出到文件，文件末尾不应有额外换行。请实现从命令行参数读取输入文件位置的功能，不要硬编码 forest.in 。

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        fo << grid[i * n + j] << " ";
    }
    fo << std::endl;
}

本题评测机的运行脚本，供参考：

. /etc/profile >/dev/null #加载环境
krun init >/dev/null
if [ "$JOB_COMPLETION_INDEX" -eq 0 ]; then
    krun host -n -H > hostfile
    mpirun --hostfile hostfile -np 64 -ppn 16 /data/forest /problem/input.dat /data/output.dat
else
    sleep infinity
fi

因为选手的 pod 本来就是 sleep infinity 开启的，所以你可以登录任意的 pod ，运行：

. /etc/profile >/dev/null #加载环境
krun init >/dev/null
krun host -n -H > hostfile
mpirun --hostfile hostfile -np 4 -ppn 1 /data/forest /problem/input.dat /data/output.dat

背景描述¶

在西西努努魔法大陆的一片神秘的森林中，生长着一种神奇的树木——呆呆树。呆呆树不仅外表呆萌，还有一个奇特的性质：它们虽然会燃烧，但永远不会完全消失！当火灾发生时，呆呆树会从树木状态转化为燃烧状态，最终变成灰烬。然而，灰烬中蕴藏着生机，在魔法的作用下，呆呆树就能从灰烬中重生！

近日，这片森林并不太平，一场火灾打破了森林的宁静。在火灾蔓延的同时，黑魔法师乌乌和善良的魔法师芙芙正在这片森林中展开一场激烈的对抗。乌乌可以使用魔法召唤惊雷，点燃森林中的某棵呆呆树，试图用火焰吞噬一切。而芙芙则不甘示弱，她可以用神奇的魔法妙手回春，让一定区域内的呆呆树灰烬重新焕发生机，从而拯救这片森林。两人的魔法在森林中交织，火势时而蔓延，时而消退，呆呆树的状态也在不断变化。

作为森林的守护者，你需要模拟火灾的蔓延过程，从而获知呆呆树的状态变化。由于森林的面积很大，为了加快模拟的速度，你想到了借助 MPI 的力量，将模拟任务分配到多个进程中并行处理。时间紧迫，快来帮助人们拯救这片森林吧！

任务描述¶

你需要模拟一个 $n \times n$ 的呆呆树森林网格，森林网格的坐标范围为 $[0, n-1] \times [0, n-1]$。每个格点可能是以下四种状态之一： - 0：空地 - 1：树木 - 2：燃烧 - 3：灰烬

呆呆树的状态会随着时间的变化而更新。模拟以时间步为粒度进行，每个时间步分为两个阶段：

1. 魔法事件阶段：
   • 在该阶段，可能会发生两种魔法事件：
     • 天降惊雷：黑魔法师乌乌在坐标 $(x, y)$ 处落下惊雷。如果坐标 $(x, y)$ 处的格点状态为树木（状态1）的话，则将其状态转化为燃烧（状态2）。
     • 妙手回春：魔法师芙芙让一片矩形区域 $[sx, sy] \times [ex, ey]$ 内的灰烬恢复生机。对于矩形区域 $[sx, sy] \times [ex, ey]$ 内（包含边界）的每一个格点，如果其状态为灰烬（状态3），则将其状态转化为树木（状态1）。
   • 如果该时间步没有魔法事件，则在魔法事件阶段中，森林的状态不会发生任何改变。
2. 状态转移阶段：
   • 在该阶段，按照以下规则进行状态转移：
     • 如果一个格点的状态是树木（状态1），且其周围（即上下左右的四个格点）中至少有一个格点的状态是燃烧（状态2），则该格点的状态会转变为燃烧（状态2）。
     • 如果一个格点的状态是燃烧（状态2），则该格点的状态会转化为灰烬（状态3）。

在同一时间步中，魔法事件阶段先发生，状态转移阶段后发生。也就是说，在同一时间步中，状态转移阶段的状态输入即为魔法事件阶段的状态输出。

你的任务是模拟火灾的蔓延过程，并输出最终每个格点的状态。

评测环境¶

容器镜像：intel。编译器已经配置为 mpiicpx，并且已经加载了 mpi 模块。

输入输出约定¶

输入格式¶

本题需要从文件读取输入。输入文件为文本文件，文件名从命令行参数获取。

输入文件的格式如下：

第一行包含三个整数 $n$、$m$ 和 $t$，分别表示网格的边长、魔法事件的数量、模拟的总时间步数。

接下来的 $n$ 行，每行包含 $n$ 个整数，表示初始时刻每个格点的状态（0：空地、1：树木、2：燃烧、3：灰烬）。

接下来 $m$ 行，每行描述一个魔法事件，格式为 "<时间步> <事件类型> <参数>"，事件类型包括：

• 天降惊雷，参数为惊雷降落处的坐标 $x$ 和 $y$ 。题目输入保证 $0 \leq x, y \leq n - 1$ 。
• 妙手回春，参数为矩形区域的范围 $sx$, $sy$, $ex$, $ey$ 。题目输入保证 $0 \leq sx \leq ex \leq n - 1$ 且 $0 \leq sy \leq ey \leq n - 1$ 。

在输入文件中，魔法事件的顺序按照其发生的时间步顺序升序排列。并且，每个时间步最多发生一个魔法事件。

你可以使用handout中的gencase.py生成测试数据。

输出格式¶

你需要把结果输出到输出文件中，文件名从命令行参数获取。

输出的格式为：输出 $n$ 行，每行包含 $n$ 个用空格分开的整数，表示最终时刻每个格点的状态。

样例输入输出¶

样例一

• 输入文件 ：

6 2 4
1 1 1 2 1 1
1 0 1 1 1 1
0 1 2 1 0 1
0 1 0 1 0 1
1 1 1 1 1 1
1 0 0 1 0 0
3 2 0 1 2 3
4 1 4 5

• 输出文件：

3 3 3 2 3 3 
2 0 2 3 3 3 
0 3 2 3 0 2 
0 3 0 3 0 2 
2 3 2 3 2 3 
1 0 0 2 0 0 

• 对样例的解释：

本样例的地图尺寸为 $6 \times 6$，发生了2个魔法事件（分别在时间步3和时间步4发生），要求输出模拟4个时间步之后的模拟结果。

森林的初始状态如下：

1 1 1 2 1 1
1 0 1 1 1 1
0 1 2 1 0 1
0 1 0 1 0 1
1 1 1 1 1 1
1 0 0 1 0 0

时间步1没有发生魔法事件，故只进行状态转移。时间步1结束后的森林状态如下：

1 1 2 3 2 1
1 0 2 2 1 1
0 2 3 2 0 1
0 1 0 1 0 1
1 1 1 1 1 1
1 0 0 1 0 0

时间步2没有发生魔法事件，故只进行状态转移。时间步2结束后的森林状态如下：

1 2 3 3 3 2
1 0 3 3 2 1
0 3 3 3 0 1
0 2 0 2 0 1
1 1 1 1 1 1
1 0 0 1 0 0

时间步3发生了类型为2的魔法事件（即"妙手回春"），范围为 $[0,2] \times [1,3]$，该范围内状态3的格点均转化为状态1。时间步3的魔法事件阶段结束后，森林状态如下：

1 2 1 1 3 2
1 0 1 1 2 1
0 1 1 1 0 1
0 2 0 2 0 1
1 1 1 1 1 1
1 0 0 1 0 0

紧接着还需要发生时间步3的状态转移阶段。时间步3结束后的森林状态如下：

2 3 2 1 3 3
1 0 1 2 3 2
0 2 1 2 0 1
0 3 0 3 0 1
1 2 1 2 1 1
1 0 0 1 0 0

时间步4发生了类型为1的魔法事件（即"天降惊雷"），坐标为 $(4,5)$，该点的状态恰好为树木（状态1），所以会转变为燃烧（状态2）。时间步4的魔法事件阶段结束后，森林状态如下：

2 3 2 1 3 3
1 0 1 2 3 2
0 2 1 2 0 1
0 3 0 3 0 1
1 2 1 2 1 2
1 0 0 1 0 0

紧接着还需要发生时间步4的状态转移阶段。时间步4结束后的森林状态如下：

3 3 3 2 3 3
2 0 2 3 3 3
0 3 2 3 0 2
0 3 0 3 0 2
2 3 2 3 2 3
1 0 0 2 0 0

即为题目要求输出的状态。

样例二

• 输入文件 forest.in ：

16 5 7
2 2 1 1 0 2 1 1 1 1 1 1 0 0 1 1
1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1
0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 0 1 0 1 1 1 2 1 0
1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 1
1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0
1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1
1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 2 1 1 1 1 1 1 0 0 1 0 1 1 1
1 1 0 0 1 1 1 1 1 0 1 1 0 1 1 1
1 2 4 0 13 2
2 1 7 9
4 2 6 2 12 13
5 2 1 8 13 11
7 1 7 0

输出文件 forest.out ：

3 3 3 3 0 3 3 3 3 3 3 3 0 0 3 3 
3 0 3 3 3 0 3 0 3 3 3 0 3 3 3 3 
0 3 3 3 3 0 3 3 3 0 3 3 3 3 3 3 
3 3 0 3 3 3 3 0 3 0 3 3 3 3 3 0 
2 3 2 3 2 3 3 3 0 0 0 3 3 3 0 1 
1 2 1 2 0 0 3 3 3 3 3 3 3 0 2 1 
2 1 1 1 2 3 3 3 3 3 3 3 3 3 3 2 
3 2 1 0 3 3 3 3 3 3 3 0 3 3 2 0 
2 1 1 1 2 3 3 0 3 3 3 3 0 2 1 0 
2 0 0 1 2 2 0 3 3 3 3 3 3 2 1 1 
3 3 3 0 3 2 2 3 3 0 3 3 2 1 1 1 
3 3 3 3 3 0 2 2 3 2 0 2 1 1 1 1 
3 3 0 3 3 3 3 2 0 1 1 1 1 1 1 1 
3 3 3 3 3 3 3 3 2 1 1 1 1 1 1 1 
3 0 3 3 3 3 3 3 3 0 0 1 0 1 1 1 
3 3 0 0 3 3 3 3 2 0 1 1 0 1 1 1 

评分标准¶

测试环境¶

本题的评测环境为：4 节点，每节点 16 个核。运行在配备 Intel® Xeon® Platinum 8358 Processor 的服务器上。每个节点配备 32GiB 内存。

测试点和评分标准¶

本题有一个测试点，规模和评分标准如下。在限制时间内得到正确结果可以得到基本分，在满分时间内得到正确结果可以得到满分，分数随时间线性变化。

提交要求¶

本题仅提交单个 .cpp 文件。再次提醒：你的程序需要能够读取同一目录下的输入文件 forest.in ，并将结果输出到同一目录下的输出文件 forest.out ，这两个文件名会通过参数传入。

评测时的编译方式为（如果 .cpp 文件的名字为 forest.cpp ）：

mpiicpx forest.cpp -O3 -xHost -o forest

评测时的运行方式为：

export I_MPI_PIN=1
export I_MPI_PIN_DOMAIN=core  
mpirun -machinefile hostfile.txt -np 64 ./forest forest.in forest.out

其中 hostfile.txt 的内容为：

node1:16
node2:16
node3:16
node4:16

附件¶

• fire-handout.tar.gz
• fire.yaml