/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 5 点
問題文
縦 N マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と呼びます。
グリッドの各マスには数字が 1 つ書かれています。はじめ、マス (i,j) には文字列 S_i の j 文字目が書かれています。
クエリを Q 個処理してください。クエリは以下の 2 種類のいずれかです。
1 i T：j=1,2,\ldots,W について、マス (i,j) に書かれている数字を T の j 文字目に変更する。2 a b c d：マス (a,b) からマス (c,d) へ、辺で隣接するマスのうち現在のマスと同じ数字が書かれたマスへの移動を繰り返すことで到達できるか判定する。
制約
- 2 \le N \le 10^5
- 2 \le W \le 10
- 1 \le Q \le 5 \times 10^4
- S_i は長さ W の数字からなる文字列
- 1 種類目のクエリについて、1 \le i \le N
- 1 種類目のクエリについて、T は長さ W の数字からなる文字列
- 2 種類目のクエリについて、1 \le a,c \le N, 1 \le b,d \le W
- 2 種類目のクエリについて、(a,b) \ne (c,d)
- 2 種類目のクエリが与えられる時点で、マス (a,b) とマス (c,d) には同じ数字が書かれている
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W Q
S_1
S_2
\vdots
S_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは以下のいずれかの形式で与えられる。
1 i T
2 a b c d
出力
2 種類目のクエリの個数を q として、q 行出力せよ。j 行目には、j 番目の 2 種類目のクエリに対する答えを、到達できるならば Yes、到達できないならば No として出力せよ。
入力例 1
4 5 5 01010 00000 99999 01010 2 1 1 2 5 2 1 1 4 1 1 3 00000 2 1 1 4 1 2 1 2 4 2
出力例 1
Yes No Yes No
はじめ、マス (1,1) からマス (2,5) へは同じ数字 0 が書かれたマスだけを通って到達できます。一方、マス (1,1) からマス (4,1) へは到達できません。
3 行目を 00000 に変更した後は、マス (1,1) からマス (4,1) へ到達できるようになります。
入力例 2
4 7 1 1112111 1212121 1211121 1222222 2 4 1 3 7
出力例 2
Yes
マス (4,1) からマス (3,7) へ、例えば次の順に移動することで到達できます。
\[ (4,1),(3,1),(2,1),(1,1),(1,2),(1,3),(2,3),(3,3),(3,4),(3,5),(2,5),(1,5),(1,6),(1,7),(2,7),(3,7) \]
Score: 5 points
Problem Statement
There is a grid with N rows and W columns. Let cell (i,j) denote the cell in the i-th row from the top and the j-th column from the left.
Each cell of the grid contains 1 digit. Initially, cell (i,j) contains the j-th character of the string S_i.
Process Q queries. Each query is of one of the following 2 types:
1 i T: For j=1,2,\ldots,W, change the digit in cell (i,j) to the j-th character of T.2 a b c d: Determine whether you can reach cell (c,d) from cell (a,b) by repeatedly moving to a cell that shares an edge with the current cell and contains the same digit as the current cell.
Constraints
- 2 \le N \le 10^5
- 2 \le W \le 10
- 1 \le Q \le 5 \times 10^4
- S_i is a string of length W consisting of digits.
- For type 1 queries, 1 \le i \le N
- For type 1 queries, T is a string of length W consisting of digits.
- For type 2 queries, 1 \le a,c \le N, 1 \le b,d \le W
- For type 2 queries, (a,b) \ne (c,d)
- When a type 2 query is given, cells (a,b) and (c,d) contain the same digit.
- All numerical values in the input are integers.
Input
The input is given from Standard Input in the following format:
N W Q
S_1
S_2
\vdots
S_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in one of the following formats:
1 i T
2 a b c d
Output
Let q be the number of type 2 queries. Print q lines. On the j-th line, print Yes if the destination can be reached in the j-th type 2 query, and No otherwise.
Sample Input 1
4 5 5 01010 00000 99999 01010 2 1 1 2 5 2 1 1 4 1 1 3 00000 2 1 1 4 1 2 1 2 4 2
Sample Output 1
Yes No Yes No
Initially, you can reach cell (2,5) from cell (1,1) by passing only through cells containing the digit 0. However, you cannot reach cell (4,1) from cell (1,1).
After changing row 3 to 00000, you can reach cell (4,1) from cell (1,1).
Sample Input 2
4 7 1 1112111 1212121 1211121 1222222 2 4 1 3 7
Sample Output 2
Yes
You can reach cell (3,7) from cell (4,1) by moving in the following order, for example:
\[ (4,1),(3,1),(2,1),(1,1),(1,2),(1,3),(2,3),(3,3),(3,4),(3,5),(2,5),(1,5),(1,6),(1,7),(2,7),(3,7) \]