AdditionalFile5556.zip

#5556. 「POI2026 R1」Dostawy

标签: 传统 | 时间限制: 6000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – I etap Dostawy

Bajtazar 正在苦练，目标是成为职业 Forkbajt 选手。Forkbajt 的比赛在一块 $n \times n$ 的棋盘上进行，行和列均从 $1$ 到 $n$ 编号。位于第 $1$ 行第 $1$ 列的格子是 Bajtazar 的城堡。其余格子上可能有障碍物 #，也可能有要塞 F，或者空地 .。

整个比赛持续 $q+1$ 天。每两个比赛日之间的夜晚，会收到一条信息：某个要塞被新建或者被拆除。

每一天，Bajtazar 都需要把消息送到当时所有存在的要塞。一天由若干回合组成。在每个回合中：

• Bajtazar 可以招募一名新英雄，并指派他从城堡出发前往某个要塞（把消息送到该要塞）。
• 之后，所有英雄（包括刚招募的）可以同时向上下左右四个方向的相邻格子移动一步。
• 英雄可以经过有要塞格子，但不能经过障碍物格子。
• 回合结束时，任何两个英雄不能站在同一个格子上。

我们关心的是：把消息送到当天所有要塞所需要的最少回合数。

请你对 $q+1$ 个比赛日分别计算当天把消息送到所有现有要塞所需的最少回合数。

保证任意时刻，每个要塞都与城堡连通（存在从城堡到该要塞的不经过障碍物的路径）。

输入格式

第一行两个整数 $n, q$ $(2 \leq n \leq 1000,\ 0 \leq q \leq 500000)$，分别表示棋盘大小和变化次数（即比赛天数为 $q+1$）。

接下来 $n$ 行，每行 $n$ 个字符，描述初始棋盘：

• # 表示障碍物
• F 表示要塞
• . 表示空地
• 第 $1$ 行第 $1$ 列一定是 Z，表示 Bajtazar 的城堡

接下来 $q$ 行，每行两个整数 $x_i, y_i$ $(1 \leq x_i, y_i \leq n)$，表示第 $i$ 个夜晚（第 $i$ 天与第 $i+1$ 天之间）在 $(x_i, y_i)$ 处要塞状态翻转：原来没有要塞的会新建，原来有要塞的会被拆除。该位置保证不是障碍物也不是城堡。

输出格式

输出 $q+1$ 行，第 $i$ 行表示第 $i$ 天把消息送到所有要塞所需的最少回合数。

样例

输入

4 3
Z...
###.
F.#F
...F
3 2
4 1
3 1

输出

10
10
11
10

在第一天（也是第一个查询），可以用 $10$ 回合把消息送到全部要塞，一种可能的英雄移动路径如下（列表示回合）：

$\begin{array}{l c c c c c c c c c c c c c c c c c c c} \textbf{英雄 1:} & (1, 2) & \to & (1, 3) & \to & (1, 4) & \to & (2, 4) & \to & (3, 4) & \to & (4, 4) & \to & (4, 3) & \to & (4, 2) & \to & (3, 2) & \to & (3, 1) \\ \textbf{英雄 2:} & & & (1, 2) & \to & (1, 3) & \to & (1, 4) & \to & (2, 4) & \to & (3, 4) & \to & (4, 4) & & & & & & \\ \textbf{英雄 3:} & & & & & (1, 2) & \to & (1, 3) & \to & (1, 4) & \to & (2, 4) & \to & (3, 4) & & & & & & \end{array}$

附加样例

1. $n=6, q=0$，除了 $(1,1)$ 城堡和 $(6,6)$ 障碍外，其余所有格子都有要塞
2. $n=1000, q=100000$，棋盘无障碍，要塞先从最远的位置逐个出现，随后按相同顺序逐个消失

数据范围与提示

详细子任务附加限制及分值如下表所示。