A map of R rows and C columns is given.
'.' is an empty cell and '#' is a wall.
You start at the top-left cell and want to reach the bottom-right cell.
Both of these cells are always empty.
One move takes you to the cell directly up, down, left or right (you cannot leave the map).
You may enter a wall cell by breaking that wall, but over the whole trip you may break at most K walls in total.
A broken wall cell becomes empty, so passing through it again does not break it again.
Breaking into a wall also counts as one move.
Print the fewest moves needed to reach the bottom-right cell.
If it cannot be reached, print -1; if the map is a single cell, print 0.
Input
The first line has R, C and K, followed by R strings of length C made only of '.' and '#'. 1 ≤ R, C ≤ 30, 0 ≤ K ≤ 10. The top-left and bottom-right cells are '.'.
Output
The fewest moves, or -1
Example 1 · stdin
4 5 1
...#.
##.#.
...#.
.###.
stdout
7
Example 2 · stdin
4 5 0
...#.
##.#.
...#.
.###.
stdout
-1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The fewest moves is breadth-first search (BFS): spread from the nearest places with a queue, and the first time you reach the goal is the answer. Running it with a stack instead (depth-first) means the first path found may be a detour. The key here is the state: on the same cell, arriving after breaking 2 walls and after breaking 0 leaves different places reachable. So mark 'visited' per (cell, walls broken), not per cell — marking only cells lets a path that broke walls and arrived first take the cell, blocking a path that broke fewer and arrived a bit later (the most common trap). There are at most 30 × 30 × 11 = 9,900 states, so adding each state once is fast. When entering a wall, check 'walls broken after entering ≤ K'; checking 'before entering ≤ K' breaks K + 1 walls. How to store states also differs: Python a 3D list [[[-1] * (k + 1) for _ in range(c)] for _ in range(r)] and tuples in a deque, Java int[r][c][k + 1] (it starts at 0, so fill -1 with Arrays.fill) and ArrayDeque<int[]>, C# new int[r, c, k + 1] (a rectangular 3D array) and a named tuple Queue<(int y, int x, int used)>, C++ three nested std::vectors and std::queue<std::tuple<int, int, int>> (unpacked with the structured binding auto [y, x, used]). C, JavaScript, TypeScript and Craykon flatten a state into one number (y * c + x) * (k + 1) + used and keep one 1D array; the queue is a list that is only appended to, read by moving a front index (head) (C and Craykon put that number in the queue, JavaScript and TypeScript put [y, x, used]). Craykon lists hold up to 10,000 items, so the ranges were chosen to keep the states at 9,900 at most. When splitting a state back in Craykon, / divides into decimals, so use Mathf.Quot(s, k + 1) and %.
Pythonmain.py · 25 lines
from collections import dequer, c, k = map(int, input().split())grid = [input().strip() for _ in range(r)]# 상태 = (칸, 지금까지 부순 벽 수). 같은 칸이라도 부순 수가 다르면 다른 상태다# dist[y][x][used] = 그 상태까지 가장 적은 이동 횟수(-1은 아직 못 감)dist = [[[-1] * (k + 1) for _ in range(c)] for _ in range(r)]dist[0][0][0] = 0queue = deque([(0, 0, 0)])answer = -1while queue: y, x, used = queue.popleft() if (y, x) == (r - 1, c - 1): answer = dist[y][x][used] # 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)): ny, nx = y + dy, x + dx if not (0 <= ny < r and 0 <= nx < c): continue nused = used + (1 if grid[ny][nx] == "#" else 0) if nused <= k and dist[ny][nx][nused] == -1: dist[ny][nx][nused] = dist[y][x][used] + 1 queue.append((ny, nx, nused))print(answer)
JavaScriptmain.js · 28 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [r, c, k] = lines[0].trim().split(/\s+/).map(Number);const grid = lines.slice(1, 1 + r).map((s) => s.trim());const STEPS = [[1, 0], [-1, 0], [0, 1], [0, -1]];// 상태 = (칸, 지금까지 부순 벽 수)를 수 하나로: (y * c + x) * (k + 1) + usedconst id = (y, x, used) => (y * c + x) * (k + 1) + used;const dist = new Array(r * c * (k + 1)).fill(-1);dist[id(0, 0, 0)] = 0;const queue = [[0, 0, 0]];let answer = -1;for (let head = 0; head < queue.length; head++) { const [y, x, used] = queue[head]; if (y === r - 1 && x === c - 1) { answer = dist[id(y, x, used)]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; const nused = used + (grid[ny][nx] === "#" ? 1 : 0); if (nused <= k && dist[id(ny, nx, nused)] === -1) { dist[id(ny, nx, nused)] = dist[id(y, x, used)] + 1; queue.push([ny, nx, nused]); } }}console.log(answer);
TypeScriptmain.ts · 30 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [r, c, k]: number[] = lines[0].trim().split(/\s+/).map(Number);const grid: string[] = lines.slice(1, 1 + r).map((s) => s.trim());const STEPS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];// 상태 = (칸, 지금까지 부순 벽 수)를 수 하나로: (y * c + x) * (k + 1) + usedconst id = (y: number, x: number, used: number): number => (y * c + x) * (k + 1) + used;const dist: number[] = new Array<number>(r * c * (k + 1)).fill(-1);dist[id(0, 0, 0)] = 0;const queue: [number, number, number][] = [[0, 0, 0]];let answer = -1;for (let head = 0; head < queue.length; head++) { const [y, x, used] = queue[head]; if (y === r - 1 && x === c - 1) { answer = dist[id(y, x, used)]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; const nused = used + (grid[ny][nx] === "#" ? 1 : 0); if (nused <= k && dist[id(ny, nx, nused)] === -1) { dist[id(ny, nx, nused)] = dist[id(y, x, used)] + 1; queue.push([ny, nx, nused]); } }}console.log(answer);
JavaMain.java · 45 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int r = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); String[] grid = new String[r]; for (int y = 0; y < r; y++) grid[y] = in.readLine().trim(); int[] dy = {1, -1, 0, 0}, dx = {0, 0, 1, -1}; // 상태 = (칸, 지금까지 부순 벽 수). 같은 칸이라도 부순 수가 다르면 다른 상태다 int[][][] dist = new int[r][c][k + 1]; for (int[][] plane : dist) for (int[] cell : plane) java.util.Arrays.fill(cell, -1); dist[0][0][0] = 0; ArrayDeque<int[]> queue = new ArrayDeque<>(); queue.addLast(new int[] {0, 0, 0}); int answer = -1; while (!queue.isEmpty()) { int[] cur = queue.pollFirst(); int y = cur[0], x = cur[1], used = cur[2]; if (y == r - 1 && x == c - 1) { answer = dist[y][x][used]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (int d = 0; d < 4; d++) { int ny = y + dy[d], nx = x + dx[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; int nused = used + (grid[ny].charAt(nx) == '#' ? 1 : 0); if (nused <= k && dist[ny][nx][nused] == -1) { dist[ny][nx][nused] = dist[y][x][used] + 1; queue.addLast(new int[] {ny, nx, nused}); } } } System.out.println(answer); }}
C#Main.cs · 47 lines
using System;using System.Collections.Generic;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int r = int.Parse(first[0]); int c = int.Parse(first[1]); int k = int.Parse(first[2]); var grid = new string[r]; for (int y = 0; y < r; y++) grid[y] = Console.ReadLine().Trim(); int[] dy = { 1, -1, 0, 0 }, dx = { 0, 0, 1, -1 }; // 상태 = (칸, 지금까지 부순 벽 수). 같은 칸이라도 부순 수가 다르면 다른 상태다 var dist = new int[r, c, k + 1]; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) for (int u = 0; u <= k; u++) dist[y, x, u] = -1; dist[0, 0, 0] = 0; var queue = new Queue<(int y, int x, int used)>(); queue.Enqueue((0, 0, 0)); int answer = -1; while (queue.Count > 0) { var (cy, cx, used) = queue.Dequeue(); if (cy == r - 1 && cx == c - 1) { answer = dist[cy, cx, used]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (int d = 0; d < 4; d++) { int ny = cy + dy[d], nx = cx + dx[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; int nused = used + (grid[ny][nx] == '#' ? 1 : 0); if (nused <= k && dist[ny, nx, nused] == -1) { dist[ny, nx, nused] = dist[cy, cx, used] + 1; queue.Enqueue((ny, nx, nused)); } } } Console.WriteLine(answer); }}
C++main.cpp · 38 lines
#include <iostream>#include <queue>#include <string>#include <tuple>#include <vector>int main() { int r, c, k; std::cin >> r >> c >> k; std::vector<std::string> grid(r); for (auto& row : grid) std::cin >> row; const int DY[4] = {1, -1, 0, 0}, DX[4] = {0, 0, 1, -1}; // 상태 = (칸, 지금까지 부순 벽 수). 같은 칸이라도 부순 수가 다르면 다른 상태다 std::vector<std::vector<std::vector<int>>> dist(r, std::vector<std::vector<int>>(c, std::vector<int>(k + 1, -1))); std::queue<std::tuple<int, int, int>> q; dist[0][0][0] = 0; q.push({0, 0, 0}); int answer = -1; while (!q.empty()) { auto [y, x, used] = q.front(); q.pop(); if (y == r - 1 && x == c - 1) { answer = dist[y][x][used]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; int nused = used + (grid[ny][nx] == '#' ? 1 : 0); if (nused <= k && dist[ny][nx][nused] == -1) { dist[ny][nx][nused] = dist[y][x][used] + 1; q.push({ny, nx, nused}); } } } std::cout << answer << "\n";}
Cmain.c · 42 lines
#include <stdio.h>#define MAXS (30 * 30 * 11)static char grid[30][32];static int dist[MAXS];static int queue[MAXS]; /* 상태마다 한 번만 넣으니 상태 수만큼이면 된다 */int main(void) { int r, c, k; scanf("%d %d %d", &r, &c, &k); for (int y = 0; y < r; y++) scanf("%31s", grid[y]); const int DY[4] = {1, -1, 0, 0}, DX[4] = {0, 0, 1, -1}; /* 상태 = (칸, 지금까지 부순 벽 수)를 수 하나로: (y * c + x) * (k + 1) + used */ int states = r * c * (k + 1); for (int s = 0; s < states; s++) dist[s] = -1; int head = 0, tail = 0, answer = -1; dist[0] = 0; queue[tail++] = 0; while (head < tail) { int s = queue[head++]; int used = s % (k + 1), cell = s / (k + 1); int y = cell / c, x = cell % c; if (y == r - 1 && x == c - 1) { answer = dist[s]; /* 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 */ break; } for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; int nused = used + (grid[ny][nx] == '#'); int ns = (ny * c + nx) * (k + 1) + nused; if (nused <= k && dist[ns] == -1) { dist[ns] = dist[s] + 1; queue[tail++] = ns; } } } printf("%d\n", answer); return 0;}
Craykonmain.cray · 55 lines
첫줄 = Console.ReadNumbers();r = 첫줄[0];c = 첫줄[1];k = 첫줄[2];grid = [];for (i = 0; i < r; i++){ grid.Add(Console.ReadLine().Trim());}DY = [1, -1, 0, 0];DX = [0, 0, 1, -1];// 상태 = (칸, 지금까지 부순 벽 수)를 수 하나로: (y * c + x) * (k + 1) + used// 상태는 많아야 30 × 30 × 11 = 9,900개라 목록 하나(10,000칸까지)에 들어간다dist = NewList(r * c * (k + 1), -1);dist[0] = 0;queue = [0];head = 0;answer = -1;while (head < queue.Count && answer == -1){ s = queue[head]; head += 1; used = s % (k + 1); cell = Mathf.Quot(s, k + 1); y = Mathf.Quot(cell, c); x = cell % c; if (y == r - 1 && x == c - 1) { answer = dist[s]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 } else { for (d = 0; d < 4; d++) { ny = y + DY[d]; nx = x + DX[d]; if (ny >= 0 && ny < r && nx >= 0 && nx < c) { nused = used; if (grid[ny][nx] == "#") { nused += 1; } ns = (ny * c + nx) * (k + 1) + nused; if (nused <= k && dist[ns] == -1) { dist[ns] = dist[s] + 1; queue.Add(ns); } } } }}Console.WriteLine(answer);