#P11810. [PA 2017] 商旅 / Osady i warownie

[PA 2017] 商旅 / Osady i warownie

题目背景

译自 Potyczki Algorytmiczne 2017 R5 Osady i warownie [A] (OSA)。3s,512M\texttt{3s,512M}

原题为函数式交互题,此处改为强制在线的传统题。

题目描述

一个长为 nn,宽为 mm 的长方形被划分为 n×mn\times m1×11\times 1 的方格。我们记第 ii 行第 jj 列的方格为 (i,j)(i,j)

每个方格可能是城镇,堡垒或者空地。商人在城镇间来往贸易,可以从一个方格移动到四连通的方格,但是不能经过堡垒

qq在线操作:

  • 1\texttt{1} rr cc:在 (r,c)(r,c) 上尝试建立一座堡垒,保证 (r,c)(r,c) 是空地。
    • 如果建立堡垒后,商人仍能从一个城镇到达任意一个城镇,则建立成功,(r,c)(r,c) 变为堡垒,输出 11
    • 否则忽略本次操作,(r,c)(r,c) 仍为空地,输出 00
  • 2\texttt{2} r1r_1 c1c_1 r2r_2 c2c_2
    • (r1,c1)(r_1,c_1) 上的城镇移动到相邻的 (r2,c2)(r_2,c_2)
    • 保证 (r1,c1)(r_1,c_1) 是城镇,(r2,c2)(r_2,c_2) 是空地。
    • 保证 r1r2+c1c2=1|r_1-r_2|+|c_1-c_2|=1

输入格式

注意,本题的输入量可能很大。

第一行两个正整数 n,mn,m

接下来 nn 行,第 ii 行一个长度为 mm 的字符串 sis_i

  • si,j=.s_{i,j}=\texttt{.},表示 (i,j)(i,j) 是空地;
  • si,j=Ws_{i,j}=\texttt{W},表示 (i,j)(i,j) 是堡垒;
  • 否则 si,j=Ks_{i,j}=\texttt{K},表示 (i,j)(i,j) 是城镇。

(n+2)(n+2) 行,一个整数 qq

接下来 qq 行,每行若干个整数,表示一次加密的操作:

  • 1\texttt{1} rr' cc',表示一次 1\texttt{1} 操作,其中 r=rkr=r'\oplus kc=ckc=c'\oplus k
  • 2\texttt{2} r1r_1' c1c_1' r2r_2' c2c_2':表示一次 2\texttt{2} 操作,其中 r1=r1kr_1=r_1'\oplus kr2=r2kr_2=r_2'\oplus kc1=c1kc_1=c_1'\oplus kc2=c2kc_2=c_2'\oplus k

这里,kk 表示这次操作,操作 1\texttt{1} 输出 11 的个数,\oplus 表示按位异或运算。

输出格式

输出一行一个 01\texttt{01} 串:对于每个 1\texttt{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

  • 1n,m1031\le n,m\le 10^3
  • 0q1060\le q\le 10^6