-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path2206.kt
112 lines (105 loc) · 4.82 KB
/
2206.kt
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
import java.io.*
import java.util.LinkedList
import java.util.Queue
import kotlin.math.min
data class Status(
val x : Int,
val y : Int,
val depth : Int,
val isWall : Boolean
)
fun main(){
val bw = BufferedWriter(OutputStreamWriter(System.out))
val br = BufferedReader(InputStreamReader(System.`in`))
val (n,m) = br.readLine().split(" ").map {it.toInt()}
val arr = ArrayList<Array<Int>>()
val q : Queue<Status> = LinkedList()
var isVisited = Array(n) {Array(m) {false} }
q.add(Status(0,0,1,false))
repeat(n){
arr.add(br.readLine().map {it.code - 48}.toTypedArray())
}
while(q.isNotEmpty()){
val status = q.poll()
if(status.x == n-1 && status.y == m-1){
println("${status.depth}")
return
}
if(status.x > 0 && arr[status.x-1][status.y] == 0 && !isVisited[status.x-1][status.y]){
isVisited[status.x-1][status.y] = true
q.add(Status(status.x-1,status.y,status.depth+1,status.isWall))
}
if(status.y > 0 && arr[status.x][status.y-1] == 0 && !isVisited[status.x][status.y-1]){
isVisited[status.x][status.y-1] = true
q.add(Status(status.x,status.y-1,status.depth+1,status.isWall))
}
if(status.x+1 < n && arr[status.x+1][status.y] == 0 && !isVisited[status.x+1][status.y]){
isVisited[status.x+1][status.y] = true
q.add(Status(status.x+1,status.y,status.depth+1,status.isWall))
}
if(status.y+1 < m && arr[status.x][status.y+1] == 0 && !isVisited[status.x][status.y+1]){
isVisited[status.x][status.y+1] = true
q.add(Status(status.x,status.y+1,status.depth+1,status.isWall))
}
if(status.x > 0 && arr[status.x-1][status.y] == 1 && !status.isWall && !isVisited[status.x-1][status.y]){
isVisited[status.x-1][status.y] = true
q.add(Status(status.x-1,status.y,status.depth+1, true))
}
if(status.y > 0 && arr[status.x][status.y-1] == 1 && !status.isWall && !isVisited[status.x][status.y-1]){
isVisited[status.x][status.y-1] = true
q.add(Status(status.x,status.y-1,status.depth+1,true))
}
if(status.x+1 < n && arr[status.x+1][status.y] == 1 && !status.isWall && !isVisited[status.x+1][status.y]){
isVisited[status.x+1][status.y] = true
q.add(Status(status.x+1,status.y,status.depth+1,true))
}
if(status.y+1 < m && arr[status.x][status.y+1] == 1 && !status.isWall && !isVisited[status.x][status.y+1]){
isVisited[status.x][status.y+1] = true
q.add(Status(status.x,status.y+1,status.depth+1,true))
}
}
isVisited = Array(n) {Array(m) {false} }
q.add(Status(n-1,m-1,1,false))
while(q.isNotEmpty()){
val status = q.poll()
if(status.x == 0 && status.y == 0){
println("${status.depth}")
return
}
if(status.x > 0 && arr[status.x-1][status.y] == 0 && !isVisited[status.x-1][status.y]){
isVisited[status.x-1][status.y] = true
q.add(Status(status.x-1,status.y,status.depth+1,status.isWall))
}
if(status.y > 0 && arr[status.x][status.y-1] == 0 && !isVisited[status.x][status.y-1]){
isVisited[status.x][status.y-1] = true
q.add(Status(status.x,status.y-1,status.depth+1,status.isWall))
}
if(status.x+1 < n && arr[status.x+1][status.y] == 0 && !isVisited[status.x+1][status.y]){
isVisited[status.x+1][status.y] = true
q.add(Status(status.x+1,status.y,status.depth+1,status.isWall))
}
if(status.y+1 < m && arr[status.x][status.y+1] == 0 && !isVisited[status.x][status.y+1]){
isVisited[status.x][status.y+1] = true
q.add(Status(status.x,status.y+1,status.depth+1,status.isWall))
}
if(status.x > 0 && arr[status.x-1][status.y] == 1 && !status.isWall && !isVisited[status.x-1][status.y]){
isVisited[status.x-1][status.y] = true
q.add(Status(status.x-1,status.y,status.depth+1, true))
}
if(status.y > 0 && arr[status.x][status.y-1] == 1 && !status.isWall && !isVisited[status.x][status.y-1]){
isVisited[status.x][status.y-1] = true
q.add(Status(status.x,status.y-1,status.depth+1,true))
}
if(status.x+1 < n && arr[status.x+1][status.y] == 1 && !status.isWall && !isVisited[status.x+1][status.y]){
isVisited[status.x+1][status.y] = true
q.add(Status(status.x+1,status.y,status.depth+1,true))
}
if(status.y+1 < m && arr[status.x][status.y+1] == 1 && !status.isWall && !isVisited[status.x][status.y+1]){
isVisited[status.x][status.y+1] = true
q.add(Status(status.x,status.y+1,status.depth+1,true))
}
}
bw.write("-1")
bw.flush()
bw.close()
}