-
Notifications
You must be signed in to change notification settings - Fork 0
/
2008_S3.java
115 lines (107 loc) · 3.5 KB
/
2008_S3.java
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
113
114
115
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Main {
static StringTokenizer st;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static String next () throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine().trim());
return st.nextToken();
}
static int readInt () throws IOException {
return Integer.parseInt(next());
}
static char readCharacter () throws IOException {
return next().charAt(0);
}
static ArrayList<Integer> result = new ArrayList<>();
public static void main(String[] args) throws IOException{
int t = readInt();
for (int z = 0; z < t; z++) {
int r = readInt(), c = readInt();
char[][] input = new char[r][c];
ArrayList<Pair>[][] adj = new ArrayList[r][c];
for (int i = 0; i < adj.length; i++) {
String line = next(); //
for (int j = 0; j < adj[i].length; j++) {
input[i][j] = line.charAt(j); //
// input[i][j] = readCharacter();
adj[i][j] = new ArrayList();
}
}
for (int i = 0; i < input.length; i++) { //adjacency matrix
for (int j = 0; j < input[i].length; j++) {
char tempChar = input[i][j];
adj[i][j].add(new Pair(i, j));
if (tempChar == '+') {
if (i != 0 && input[i-1][j] != '*') {
adj[i][j].add(new Pair(i - 1, j));
}
if (i != input.length - 1 && input[i+1][j] != '*') {
adj[i][j].add(new Pair(i + 1, j));
}
if (j != 0 && input[i][j-1] != '*') {
adj[i][j].add(new Pair(i, j - 1));
}
if (j != input[i].length - 1 && input[i][j+1] != '*') {
adj[i][j].add(new Pair(i, j + 1));
}
}else if (tempChar == '-') {
if (j != 0 && input[i][j-1] != '*') {
adj[i][j].add(new Pair(i, j - 1));
}
if (j != input[i].length - 1 && input[i][j+1] != '*') {
adj[i][j].add(new Pair(i, j + 1));
}
}else if (tempChar == '|') {
if (i != 0 && input[i-1][j] != '*') {
adj[i][j].add(new Pair(i - 1, j));
}
if (i != input.length - 1 && input[i+1][j] != '*') {
adj[i][j].add(new Pair(i + 1, j));
}
}
}
}
//adj[][] is an adjacency matrix storing Pairs where it can lead to
Queue<ArrayList<Pair>> q = new LinkedList();
int[][] dis = new int[r][c]; //shortest distance from the starting house
boolean[][] vis = new boolean[r][c]; //keep track if visited
Pair[][] pre = new Pair[r][c];
q.add(adj[0][0]); //push the house starting with into the queue
vis[0][0] = true; //mark the starting house visited
dis[0][0] = 0; //distance from starting house is 0
pre[0][0] = new Pair(0, 0);
while (!q.isEmpty()) {
ArrayList<Pair> cur = q.poll(); //get the head of the queue
if (!cur.isEmpty()) {
Pair coordinateOfCur = cur.get(0);
for (int i = 1; i < cur.size(); i++) { //for each pair (representing a place cur leads to)
Pair pair = cur.get(i);
int x = pair.x;
int y = pair.y;
pre[x][y] = new Pair(coordinateOfCur.x, coordinateOfCur.y);
if (!vis[x][y]) {
q.add(adj[x][y]);
vis[x][y] = true;
dis[x][y] = dis[pre[x][y].x][pre[x][y].y] + 1;
}
}
}
}
if (vis[r-1][c-1]) {
result.add(dis[r - 1][c - 1] + 1);
}else {
result.add(-1);
}
}
for (int i = 0; i < result.size(); i++) {System.out.println(result.get(i));}
}
static class Pair{
int x, y;
Pair (int po, int vo){
x = po; y = vo;
}
}
}