题目描述

题目译自 PA 2017 Runda 5 Osady i warownie

并非所有人都知道，在拜托西亚的行政边界内有一座比特克岛。由于税收极低，这座岛屿成为了来自世界各地的商人的圣地。然而，由于其在千兆字节海上的战略位置，岛屿成为敌对国家觊觎的目标。这使得岛上不仅需要组织商人聚落的基础设施，还需要建立令人印象深刻的要塞和其他防御建筑网络。

岛屿呈矩形，边长分别为 $n$ 和 $m$ 公里。拜托西亚政府决定将岛屿划分为 $n \cdot m$ 个行政区域，每个区域为边长一公里的正方形。划分中的行编号为从 $1$ 到 $n$ 的自然数，列编号为从 $1$ 到 $m$。每个区域可能是一个商人聚落、要塞，或者是森林和农业用地。商人无权进入防御建筑，但可以在其他区域自由移动。只能在相邻区域之间移动（即共享边界的区域）。

由于保持贸易的连续性至关重要，拜托西亚政府颁布了一项法令，要求任意两个现有聚落之间始终存在一条可通行的路径（可能经过其他聚落或农业用地）。然而，维护这项法令并不容易。每隔一段时间，拜托西亚国防部会提出在农业用地上建造新要塞的请求。政府会检查新建要塞是否会与法令冲突。如果没有问题，请求将被批准并实施。此外，有时聚落的居民会认为当前位置不理想，提出将聚落迁移到相邻行政区域的请求。这种请求会立即得到执行。

你受委托开发一个函数库，能够高效评估是否接受一系列请求会与拜托西亚政府的法令相冲突。

交互方式

作为任务的解决方案，你应提供一个函数库，实现以下描述的函数，供评测程序调用。为此，你的程序需包含以下语句：

#include "osalib.h"

你需要实现以下函数：

• void NowaWyspa(int n, int m, char **board) - 该函数由评测程序在程序开始时调用一次。通知你的函数库岛屿的尺寸 $(n \times m)$，并提供所有行政区域的当前使用情况。对于 $1 \leq i \leq n$，$1 \leq j \leq m$，字符 board[i-1][j-1] 描述位置 $(i, j)$ 的使用类型，取值为：
  • .（点号），表示农业用地；
  • W，表示要塞；
  • K，表示商人聚落。
• int NowaWarownia(int r, int c) - 请求在坐标 $(r, c)$ 的区域建造新要塞。你可以假设指定位置目前是农业用地。如果当前可以依据规则建造要塞，函数应返回 $1$，且要塞会立即建造；否则返回 $0$。
• void PrzeniesOsade(int r1, int c1, int r2, int c2) - 请求将商人聚落从位置 $(r_{1}, c_{1})$ 迁移到位置 $(r_{2}, c_{2})$。你可以假设 $(r_{1}, c_{1})$ 原本是聚落，$(r_{2}, c_{2})$ 原本未被占用，且两位置相邻，即 $|r_{1} - r_{2}| + |c_{1} - c_{2}| = 1$。操作后，$(r_{1}, c_{1})$ 变为农业用地，$(r_{2}, c_{2})$ 变为聚落。

函数库若对所有 NowaWarownia 查询均正确回答，则可获得该测试的得分。你的函数库不应实现 main 函数——这将由评测程序完成。此外，函数库不得从标准输入读取数据或向标准输出写入数据，否则可能导致运行错误或评测程序报告错误答案。但可以向标准错误输出写入诊断信息，请注意这会消耗时间。

示例评测程序

在「文件」页面，你可以找到函数库头文件 osalib.h 以及运行函数库示例测试的程序 osarunner.c。要编译代码（C 语言的 osalib.c 或 C++ 的 osalib.cpp），需将所有文件置于同一目录下，然后执行以下命令：

• C: gcc -std=c11 -static -O2 osalib.c osarunner.c -lm
• C++: g++ -std=c++11 -static -O2 osalib.cpp osarunner.c

生成的可执行文件会针对每个 NowaWarownia 查询输出 TAK 或 NIE，表示函数库是否同意建造要塞。

样例

数据范围与提示

对于所有数据，$1 \leq n, m \leq 1000$。此外，NowaWarownia 和 PrzeniesOsade 函数的调用次数均不超过 $1000000$ 次。