R 行 C 列の地図が与えられる。
'.' は空きマス、'#' は壁である。
左上のマスから出発して右下のマスまで行きたい。
この二つのマスは必ず空きマスである。
一回動くと、上下左右に接する一マスへ移る（地図の外には出られない）。
壁のマスには、その壁を壊して入ることができるが、道のり全体で壊せる壁は合計 K 個までである。
一度壊した壁のマスは空きマスになり、もう一度通っても壊したことにはならない。
壁を壊して入ることも一回の移動と数える。
右下のマスまで行く最小の移動回数を出力せよ。
行けなければ -1 を出力し、地図が一マスだけなら 0 を出力する。
4 5 1 ...#. ##.#. ...#. .###.
7
4 5 0 ...#. ##.#. ...#. .###.
-1
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
最小の移動回数は幅優先探索（BFS）：キューで近いところから広がれば、ゴールに最初に着いたときが答えです。
キューの代わりにスタックで回す（深さ優先）と、最初に見つけた道が遠回りかもしれません。
この問題の要は状態です：同じマスでも、壁を 2 個壊して来たのと 0 個で来たのとでは、この先行ける場所が違います。
そこで「行った」印をマスではなく（マス、壊した壁の数）ごとにつけます — マスだけに印をつけると、壁を壊して先に来た道がそのマスを取ってしまい、壊した数が少なく少し遅れて来た道がふさがれます（いちばん多い罠）。
状態は最大 30 × 30 × 11 = 9,900 個なので、状態ごとに一回だけ入れれば速いです。
壁に入るときは「入った後の壊した数 ≤ K」を見ます；「入る前の数 ≤ K」で見ると K + 1 個壊してしまいます。
状態の持ち方も言語ごとに違います：Python は三次元リスト [[[-1] * (k + 1) for _ in range(c)] for _ in range(r)] と deque のタプル、Java int[r][c][k + 1]（作ると 0 なので Arrays.fill で -1 を埋めます）と ArrayDeque<int[]>、C# new int[r, c, k + 1]（矩形の三次元配列）と名前付きタプル Queue<(int y, int x, int used)>、C++ は三重の std::vector と std::queue<std::tuple<int, int, int>>（構造化束縛 auto [y, x, used] で取り出します）。
C・JavaScript・TypeScript・Craykon は状態を一つの数 (y * c + x) * (k + 1) + used に広げて一次元配列一つに入れ、キューはリストの末尾に足すだけにして先頭位置（head）を動かしながら取り出します（C・Craykon はキューにもその数を、JavaScript・TypeScript は [y, x, used] を入れます）。
Craykon のリストは 10,000 個までなので、状態の数が最大 9,900 になるように範囲を決めました。
Craykon で状態を分け直すときは / が小数まで割るので 数学.商(s, k + 1) と % を使います。
from collections import deque r, 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)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);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);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); }}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); }}#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";}#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;}첫줄 = コンソール.数読み();r = 첫줄[0];c = 첫줄[1];k = 첫줄[2];grid = [];繰り返す (i = 0; i < r; i++){ grid.追加(コンソール.行読み().空白除去());}DY = [1, -1, 0, 0];DX = [0, 0, 1, -1]; // 상태 = (칸, 지금까지 부순 벽 수)를 수 하나로: (y * c + x) * (k + 1) + used// 상태는 많아야 30 × 30 × 11 = 9,900개라 목록 하나(10,000칸까지)에 들어간다dist = 新リスト(r * c * (k + 1), -1);dist[0] = 0;queue = [0];head = 0;answer = -1;間 (head < queue.個数 && answer == -1){ s = queue[head]; head += 1; used = s % (k + 1); cell = 数学.商(s, k + 1); y = 数学.商(cell, c); x = cell % c; もし (y == r - 1 && x == c - 1) { answer = dist[s]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 } でなければ { 繰り返す (d = 0; d < 4; d++) { ny = y + DY[d]; nx = x + DX[d]; もし (ny >= 0 && ny < r && nx >= 0 && nx < c) { nused = used; もし (grid[ny][nx] == "#") { nused += 1; } ns = (ny * c + nx) * (k + 1) + nused; もし (nused <= k && dist[ns] == -1) { dist[ns] = dist[s] + 1; queue.追加(ns); } } } }}コンソール.書く(answer);