[Link] https://www.acmicpc.net/problem/2206
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
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String[] line = br.readLine().split(" ");
int n = toi(line[0]), m = toi(line[1]);
boolean[][] canpass = new boolean[n][m];
int[] di = new int[]{ 1, 0, -1, 0 }, dj = new int[] { 0, 1, 0, -1 };
boolean[][][] visited = new boolean[n][m][2];
for(int i = 0; i < n; i++) {
String newLine = br.readLine();
for(int j = 0; j < m; j++) if(newLine.charAt(j) == '0') canpass[i][j] = true;
}
Queue<Info> q = new LinkedList<>();
q.add(new Info(0, 0, 1, true));
while(!q.isEmpty()) {
Info info = q.poll();
int ii = info.i, ij = info.j;
if(ii == n - 1 && ij == m - 1) {
print(info.cnt);
return;
}
for(int i = 0; i < 4; i++) {
int I = ii + di[i], J =ij + dj[i];
if(I >= n || I < 0 || J >= m || J < 0 || visited[I][J][0] && visited[I][J][1]) continue;
if(canpass[I][J]) {
if(!visited[I][J][0] && info.cb) {
q.add(new Info(I, J , info.cnt + 1, true));
visited[I][J][0] = true;
}
else if(!visited[I][J][1] && !info.cb) {
q.add(new Info(I, J , info.cnt + 1, false));
visited[I][J][1] = true;
}
} else {
if(!visited[I][J][1] && info.cb) {
q.add(new Info(I, J , info.cnt + 1, false));
visited[I][J][1] = true;
}
}
}
}
print(-1);
}
static class Info {
int i;
int j;
int cnt;
boolean cb;
Info(int i , int j, int cnt, boolean cb) {
this.i = i;
this.j = j;
this.cnt = cnt;
this.cb = cb;
}
}
static int toi(String s) { return Integer.parseInt(s); }
static <T> void print(T s) { System.out.print(s); }
static <T> void println(T s) { System.out.println(s); }
}