给出一张 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);