(JS,TS) 백준 - 2206.벽 부수고 이동하기

const fs = require('fs')
const stdin: string = (process.platform === 'linux'
  ? fs.readFileSync('/dev/stdin').toString()
  : `4 4 3
0111
1111
1111
1110`
).split('\n')

const input = (() => {
  let line = 0
  return () => stdin[line++]
})()

const [n, m, k] = input()
  .split(' ')
  .map((str) => parseInt(str))

const map = new Array(n).fill(0).map(() =>
  input()
    .split('')
    .map((str) => parseInt(str))
)

const dx = [0, 0, 1, -1]
const dy = [1, -1, 0, 0]

const visited = new Array(n)
  .fill(0)
  .map(() => new Array(m).fill(0).map(() => new Array(k + 1).fill(false)))
const queue: { x: number; y: number; cost: number; k: number }[] = []

queue.push({ x: 0, y: 0, cost: 1, k })

let result = -1
while (queue.length) {
  const { x, y, cost, k } = queue.shift()

  if (x === n - 1 && y === m - 1) {
    result = cost
    break
  }
  if (visited[x][y][k] === true) continue

  visited[x][y][k] = true

  for (let i = 0; i < dx.length; i++) {
    const next = { x: x + dx[i], y: y + dy[i], cost: cost + 1, k }
    if (next.x < 0 || next.x >= n || next.y < 0 || next.y >= m) continue
    // if (visited[next.x][next.y][next.k]) continue
    if (map[next.x][next.y] === 1) {
      if (k > 0) next.k -= 1
      else continue
    }
    queue.push(next)
  }
}

console.log(result)