-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.java
More file actions
119 lines (91 loc) · 2.18 KB
/
Solution.java
File metadata and controls
119 lines (91 loc) · 2.18 KB
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
116
117
118
119
import java.util.Scanner;
public class Solution{
static int [][]offset ={{1,0},{0,-1},{-1,0},{0,1}};
static Node []data = new Node[1000] ;
static Node star = new Node();
static Node end = new Node();
static int min=0;
static boolean find = false;
static int map[][] = {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 0, 0, 1, 1, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 0, 1, 1 },
{ 1, 0, 0, 0, 0, 1, 0, 0, 1 },
{ 1, 1, 0, 1, 0, 1, 0, 0, 1 },
{ 1, 1, 0, 1, 0, 1, 0, 0, 1 },
{ 1, 1, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
public static class Node{
int x;
int y;
int step;
boolean visit;
}
static int tail;
static int head;
static boolean [][]visit = new boolean[9][9];
static void init(){
for (int i=0;i<9;i++)
for (int j=0;j<9;j++){
visit[i][j]=false;
}
find = false;
head = tail = 0;
min =0;
}
static void push(Node value){
data[tail++] = value;
}
static Node pop(){
return data[head++];
}
static void BFS(){
Node curnode;
while(head < tail){
curnode = pop();
for(int k=0;k<4;k++){
Node newnode = new Node();
newnode.x = curnode.x+ offset[k][0];
newnode.y = curnode.y+ offset[k][1];
if(newnode.x>=0 && newnode.x<9 &&newnode.y>=0 &&newnode.y<9
&& visit[newnode.x][newnode.y] == false){
if(map[newnode.x][newnode.y]!=1){
visit[newnode.x][newnode.y] = true;
newnode.step = curnode.step+1;
newnode.visit = true;
if(newnode.x == end.x && newnode.y == end.y){
min = curnode.step+1;
find = true;
break;
}
push(newnode);
}
}
}
if(find){
break;
}
}
}
public static void main(String[] args)throws Exception {
int T,x,y;
Scanner sc;
//System.setIn(new java.io.FileInputStream("src/input.txt"));
sc = new Scanner(System.in);
T= sc.nextInt();
for(int t=0;t<T;t++){
init();
star.x = sc.nextInt();
star.y = sc.nextInt();
star.step = 0;
star.visit = true;
end.x = sc.nextInt();
end.y = sc.nextInt();
visit[star.x][star.y]= true;
push(star);
BFS();
System.out.println(min);
}
}
}