[Link] https://AtCoder.jp/contests/typical90/tasks/typical90_l
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
import java.util.*;
import java.io.*;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int h, w, q;
static int[][] link;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
readLine();
h = getInt();
w = getInt();
readLine();
q = getInt();
link = new int[h + 1][w + 1];
StringBuilder sb = new StringBuilder();
int cnt = 0;
for(int i = 0; i < q; i++) {
readLine();
int t = getInt();
if(t == 1) {
int y = getInt(), x = getInt(), count = 0, val = 0;
ArrayList<Integer> al = new ArrayList<>();
for(int j = 0; j < 4; j++) {
int py = y + dy[j], px = x + dx[j];
if(inRange(py, px) && link[py][px] > 0) {
al.add(j);
if(val == 0) val = link[py][px];
count++;
}
}
if(count == 0) {
link[y][x] = ++cnt;
}
else if(count == 1) link[y][x] = val;
else {
link[y][x] = val;
for(int idx = 0; idx < al.size(); idx++) {
int j = al.get(idx);
if(link[y + dy[j]][x + dx[j]] != val) {
repaint(y + dy[j], x + dx[j], val);
}
}
}
} else {
int y1 = getInt(), x1 = getInt(), y2 = getInt(), x2 = getInt();
if(link[y1][x1] > 0 && link[y1][x1] == link[y2][x2]) sb.append("Yes\n");
else sb.append("No\n");
}
}
System.out.print(sb);
}
static void repaint(int i, int j, int paintVal) {
boolean[][] visited = new boolean[h + 1][w + 1];
Queue<int[]> q = new LinkedList<>();
int origVal = link[i][j];
q.add(new int[] { i , j });
while(!q.isEmpty()) {
int[] bot = q.poll();
if(visited[bot[0]][bot[1]]) continue;
visited[bot[0]][bot[1]] = true;
link[bot[0]][bot[1]] = paintVal;
for(int l = 0; l < 4; l++) {
int y = bot[0] + dy[l], x = bot[1] + dx[l];
if(!inRange(y, x)) continue;
if(!visited[y][x] && link[y][x] == origVal) {
q.add(new int[] { y, x });
}
}
}
}
static boolean inRange(int i, int j) {
return i >= 1 && j >= 1 && i <= h && j <= w;
}
static int getInt() { return Integer.parseInt(st.nextToken()); }
static void readLine() throws IOException { st = new StringTokenizer(br.readLine()); }
}
TLE(BFS) code(below)
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
import java.util.*;
import java.io.*;
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static boolean[][] colored;
static int h, w, q;
public static void main(String[] args) throws IOException {
readLine();
h = getInt();
w = getInt();
readLine();
q = getInt();
colored = new boolean[h + 1][w + 1];
StringBuilder sb = new StringBuilder();
int qcnt = 1;
for(int i = 0; i < q; i++) {
readLine();
int t = getInt();
if(t == 1) {
int y = getInt(), x = getInt();
colored[y][x] = true;
} else {
int y1 = getInt(), x1 = getInt(), y2 = getInt(), x2 = getInt();
if(colored[y1][x1] && colored[y2][x2] && isConnected(y1, x1, y2, x2)) sb.append("Yes\n");
else sb.append("No\n");
}
}
System.out.print(sb);
}
static boolean isConnected(int i, int j, int di, int dj) {
if(i == di && j == dj) return true;
boolean[][] visited = new boolean[h + 1][w + 1];
Queue<int[]> q = new LinkedList<>();
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
q.add(new int[] { i , j });
while(!q.isEmpty()) {
int[] bot = q.poll();
if(visited[bot[0]][bot[1]]) continue;
visited[bot[0]][bot[1]] = true;
for(int l = 0; l < 4; l++) {
int y = bot[0] + dy[l], x = bot[1] + dx[l];
if(!inRange(y, x)) continue;
if(!visited[y][x] && colored[y][x]) {
if(y == di && x == dj) return true;
q.add(new int[] { y, x });
}
}
}
return false;
}
static boolean inRange(int i, int j) {
return i >= 1 && j >= 1 && i <= h && j <= w;
}
static int getInt() { return Integer.parseInt(st.nextToken()); }
static void readLine() throws IOException { st = new StringTokenizer(br.readLine()); }
}