题目背景
译自 Potyczki Algorytmiczne 2017 R5 Osady i warownie [A] (OSA)。3s,512M。
原题为函数式交互题,此处改为强制在线的传统题。
题目描述
一个长为 n,宽为 m 的长方形被划分为 n×m 个 1×1 的方格。我们记第 i 行第 j 列的方格为 (i,j)。
每个方格可能是城镇,堡垒或者空地。商人在城镇间来往贸易,可以从一个方格移动到四连通的方格,但是不能经过堡垒。
有 q 次在线操作:
- 1 r c:在 (r,c) 上尝试建立一座堡垒,保证 (r,c) 是空地。
- 如果建立堡垒后,商人仍能从一个城镇到达任意一个城镇,则建立成功,(r,c) 变为堡垒,输出 1;
- 否则忽略本次操作,(r,c) 仍为空地,输出 0。
- 2 r1 c1 r2 c2:
- 将 (r1,c1) 上的城镇移动到相邻的 (r2,c2)。
- 保证 (r1,c1) 是城镇,(r2,c2) 是空地。
- 保证 ∣r1−r2∣+∣c1−c2∣=1。
输入格式
注意,本题的输入量可能很大。
第一行两个正整数 n,m。
接下来 n 行,第 i 行一个长度为 m 的字符串 si:
- si,j=.,表示 (i,j) 是空地;
- si,j=W,表示 (i,j) 是堡垒;
- 否则 si,j=K,表示 (i,j) 是城镇。
第 (n+2) 行,一个整数 q。
接下来 q 行,每行若干个整数,表示一次加密的操作:
- 1 r′ c′,表示一次 1 操作,其中 r=r′⊕k,c=c′⊕k。
- 2 r1′ c1′ r2′ c2′:表示一次 2 操作,其中 r1=r1′⊕k,r2=r2′⊕k,c1=c1′⊕k,c2=c2′⊕k。
这里,k 表示这次操作前,操作 1 输出 1 的个数,⊕ 表示按位异或运算。
输出格式
输出一行一个 01 串:对于每个 1 操作,输出一行一个整数,表示答案。
3 4
..WK
WK..
...K
5
1 3 2
1 3 2
2 3 3 3 2
2 3 2 2 2
1 3 2
101
提示
样例解释
加密前的样例:
3 4
..WK
WK..
...K
5
1 3 2
1 2 3
2 2 2 2 3
2 2 3 3 3
1 2 3
- 1≤n,m≤103;
- 0≤q≤106。