Initially, every cell is white. Each operation either paints a cell red or asks whether two cells are connected using only red cells and four-directional moves. Print Yes if both queried cells are red and one can reach the other; otherwise print No.
Treat every grid cell as an element of a disjoint-set union (DSU), and keep a separate red array to record which cells have been painted. When a cell is painted for the first time, activate it and unite it with each in-bounds red neighbor. Cells never become white again, so connectivity only merges; the DSU therefore continues to represent the connected components of all red cells.
For a query, first require both cells to be red, then compare their DSU representatives. The explicit red check ensures that an unpainted cell is not considered connected even to itself. Neighbor coordinates are checked before accessing the grid.
With path compression and union by size, each DSU operation takes amortized O(α(HW)) time. Every cell is activated at most once and has only four neighbors to inspect, so the total time is O((HW + Q) α(HW)). The DSU and red-cell array use O(HW) space.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import java.io.*;
public class Main {
static class FastScanner {
private final InputStream input;
private final byte[] buffer = new byte[1 << 16];
private int length = 0;
private int pointer = 0;
FastScanner(InputStream input) {
this.input = input;
}
private int read() throws IOException {
if (pointer == length) {
length = input.read(buffer);
pointer = 0;
if (length == -1) return -1;
}
return buffer[pointer++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
static class DSU {
private final int[] parent;
private final int[] size;
DSU(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) return;
if (size[rootA] < size[rootB]) {
int temp = rootA;
rootA = rootB;
rootB = temp;
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
}
}
static final int[] DR = {-1, 1, 0, 0};
static final int[] DC = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner(System.in);
int h = input.nextInt();
int w = input.nextInt();
int q = input.nextInt();
int cells = h * w;
boolean[] red = new boolean[cells];
DSU dsu = new DSU(cells);
StringBuilder output = new StringBuilder();
for (int i = 0; i < q; i++) {
int type = input.nextInt();
if (type == 1) {
int r = input.nextInt() - 1;
int c = input.nextInt() - 1;
int cell = r * w + c;
if (!red[cell]) {
red[cell] = true;
for (int direction = 0; direction < 4; direction++) {
int nr = r + DR[direction];
int nc = c + DC[direction];
if (nr >= 0 && nr < h && nc >= 0 && nc < w) {
int neighbor = nr * w + nc;
if (red[neighbor]) dsu.unite(cell, neighbor);
}
}
}
} else {
int r1 = input.nextInt() - 1;
int c1 = input.nextInt() - 1;
int r2 = input.nextInt() - 1;
int c2 = input.nextInt() - 1;
int first = r1 * w + c1;
int second = r2 * w + c2;
output.append(red[first] && red[second] && dsu.find(first) == dsu.find(second) ? "Yes" : "No").append('\n');
}
}
System.out.print(output);
}
}