문제풀이
- h, w, d(가로, 세로 방향)를 고려하며 bfs로 최소 횟수를 구한다.
주의사항
소요시간
15분
package AtCoder.ABC.ABC387.D
fun main() {
val (H, W) = readln().trim().split(" ").map(String::toInt)
val matrix = List(H) { readln().trim().toCharArray() }
fun bfs(sr: Int, sc: Int, er: Int, ec: Int): Int {
var count = 0
val queue = ArrayDeque<Triple<Int, Int, Int>>()
val visited = List(H) { List(W) { BooleanArray(2) } }
fun isValid(r: Int, c: Int) = r in 0 until H && c in 0 until W && matrix[r][c] != '#'
fun visit(r: Int, c: Int, d: Int) {
if (!isValid(r, c) || visited[r][c][d]) return
visited[r][c][d] = true
queue.add(Triple(r, c, d))
}
visit(sr, sc, 0)
visit(sr, sc, 1)
while (queue.isNotEmpty()) {
repeat(queue.size) {
val (r, c, d) = queue.removeFirst()
if (r == er && c == ec) return count
if (d == 0) {
visit(r + 1, c, 1)
visit(r - 1, c, 1)
} else {
visit(r, c + 1, 0)
visit(r, c - 1, 0)
}
}
count++
}
return -1
}
fun bfs(sr: Int, sc: Int): Int {
for (i in 0 until H) {
for (j in 0 until W) {
if (matrix[i][j] == 'G') return bfs(sr, sc, i, j)
}
}
return -1
}
fun result(): Int {
for (i in 0 until H) {
for (j in 0 until W) {
if (matrix[i][j] == 'S') return bfs(i, j)
}
}
return -1
}
println(result())
}