You are given a grid of size rows × cols representing a haunted castle. Some cells are walls (impassable), and there are designated endpoints (start and exit). Each step you can move to an orthogonally adjacent cell (up/down/left/right) that is not a wall.
Implement classes/functions to represent the grid, walls, and endpoints, plus a function that finds a path from the start to the exit through valid cells and reports the sequence of cells visited.
Example: rows=2, cols=2, walls=[[0,1]], start=[0,0], end=[1,1] → [(0,0),(1,0),(1,1)] (length 3 = 2 steps).
解法
在 4 邻域上从 start 到 end 做标准 BFS，用 parent 表回溯路径；跳过墙和越界。复杂度 O(rows·cols)。
from collections import deque
def escape(rows, cols, walls, start, end):
blocked = set(map(tuple, walls))
if start in blocked or end in blocked:
return []
if start == end:
return [start]
parent = {start: None}
q = deque([start])
while q:
r, c = q.popleft()
if (r, c) == end:
path, cur = [], end
while cur is not None:
path.append(cur)
cur = parent[cur]
return path[::-1]
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols \
and (nr, nc) not in blocked and (nr, nc) not in parent:
parent[(nr, nc)] = (r, c)
q.append((nr, nc))
return []import java.util.*;
class Solution {
static List<int[]> escape(int rows, int cols, int[][] walls, int[] start, int[] end) {
Set<Long> blocked = new HashSet<>();
for (int[] w : walls) blocked.add((long) w[0] * cols + w[1]);
long sk = (long) start[0] * cols + start[1];
long ek = (long) end[0] * cols + end[1];
if (blocked.contains(sk) || blocked.contains(ek)) return new ArrayList<>();
Map<Long, long[]> parent = new HashMap<>();
parent.put(sk, null);
Deque<int[]> q = new ArrayDeque<>();
q.offer(start);
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
long ck = (long) cur[0] * cols + cur[1];
if (ck == ek) {
List<int[]> path = new ArrayList<>();
long c = ek;
while (true) {
path.add(new int[]{(int) (c / cols), (int) (c % cols)});
long[] p = parent.get(c);
if (p == null) break;
c = p[0] * cols + p[1];
}
Collections.reverse(path);
return path;
}
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
long nk = (long) nr * cols + nc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !blocked.contains(nk) && !parent.containsKey(nk)) {
parent.put(nk, new long[]{cur[0], cur[1]});
q.offer(new int[]{nr, nc});
}
}
}
return new ArrayList<>();
}
}#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> escape(int rows, int cols,
vector<pair<int,int>>& walls,
pair<int,int> start, pair<int,int> end) {
set<pair<int,int>> blocked(walls.begin(), walls.end());
if (blocked.count(start) || blocked.count(end)) return {};
if (start == end) return {start};
map<pair<int,int>, pair<int,int>> parent;
parent[start] = {-1, -1};
queue<pair<int,int>> q;
q.push(start);
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (make_pair(r, c) == end) {
vector<pair<int,int>> path;
auto cur = end;
while (cur.first != -1) { path.push_back(cur); cur = parent[cur]; }
reverse(path.begin(), path.end());
return path;
}
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
pair<int,int> np = {nr, nc};
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !blocked.count(np) && !parent.count(np)) {
parent[np] = {r, c};
q.push(np);
}
}
}
return {};
}In Part 2, the castle now contains treasures. Each treasure can only be picked up once. Your objective is to escape in as few moves as possible and maximize the number of treasures collected along the way. Define a Treasure class (with position) and implement escape() that returns (min_steps, max_treasures). If unreachable, return (-1, 0).
Example: rows=3, cols=3, walls=[[1,1]], treasures=[[0,1]], start=[0,0], end=[2,2] → (4, 1).
解法
两阶段：阶段 1 用 BFS 算每格到 start 的最短距离；阶段 2 按距离升序处理每格做 DP f[r][c] = max(f[parent]) + (1 if treasure else 0)，parent 是距离为 dist[r][c] - 1 的任意邻居。答案为 (dist[end], f[end])。复杂度 O(rows·cols)。
from collections import deque
def escape_two_phase(rows, cols, walls, treasures, start, end):
blocked = set(map(tuple, walls))
tr = set(map(tuple, treasures))
INF = float('inf')
dist = [[INF] * cols for _ in range(rows)]
dist[start[0]][start[1]] = 0
q = deque([start])
while q:
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in blocked and dist[nr][nc] == INF:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
if dist[end[0]][end[1]] == INF:
return (-1, 0)
D = dist[end[0]][end[1]]
f = [[-1] * cols for _ in range(rows)]
f[start[0]][start[1]] = 1 if start in tr else 0
layer = [[] for _ in range(D + 1)]
for r in range(rows):
for c in range(cols):
if dist[r][c] <= D:
layer[dist[r][c]].append((r, c))
for d in range(1, D + 1):
for (r, c) in layer[d]:
best = -1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
pr, pc = r + dr, c + dc
if 0 <= pr < rows and 0 <= pc < cols and dist[pr][pc] == d - 1 and f[pr][pc] >= 0:
best = max(best, f[pr][pc])
if best >= 0:
f[r][c] = best + (1 if (r, c) in tr else 0)
return (D, f[end[0]][end[1]])import java.util.*;
class Solution {
static int[] escapeTwoPhase(int rows, int cols, int[][] walls, int[][] treasures, int[] start, int[] end) {
boolean[][] blocked = new boolean[rows][cols];
for (int[] w : walls) blocked[w[0]][w[1]] = true;
boolean[][] tr = new boolean[rows][cols];
for (int[] t : treasures) tr[t[0]][t[1]] = true;
int INF = Integer.MAX_VALUE / 2;
int[][] dist = new int[rows][cols];
for (int[] row : dist) Arrays.fill(row, INF);
dist[start[0]][start[1]] = 0;
Deque<int[]> q = new ArrayDeque<>();
q.offer(start);
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !blocked[nr][nc] && dist[nr][nc] == INF) {
dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
q.offer(new int[]{nr, nc});
}
}
}
int D = dist[end[0]][end[1]];
if (D >= INF) return new int[]{-1, 0};
int[][] f = new int[rows][cols];
for (int[] row : f) Arrays.fill(row, -1);
f[start[0]][start[1]] = tr[start[0]][start[1]] ? 1 : 0;
List<List<int[]>> layer = new ArrayList<>();
for (int i = 0; i <= D; i++) layer.add(new ArrayList<>());
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (dist[r][c] <= D) layer.get(dist[r][c]).add(new int[]{r, c});
for (int d = 1; d <= D; d++) {
for (int[] cell : layer.get(d)) {
int best = -1;
for (int[] dd : dirs) {
int pr = cell[0] + dd[0], pc = cell[1] + dd[1];
if (pr >= 0 && pr < rows && pc >= 0 && pc < cols
&& dist[pr][pc] == d - 1 && f[pr][pc] >= 0)
best = Math.max(best, f[pr][pc]);
}
if (best >= 0) f[cell[0]][cell[1]] = best + (tr[cell[0]][cell[1]] ? 1 : 0);
}
}
return new int[]{D, f[end[0]][end[1]]};
}
}#include <bits/stdc++.h>
using namespace std;
pair<int,int> escapeTwoPhase(int rows, int cols,
vector<pair<int,int>>& walls,
vector<pair<int,int>>& treasures,
pair<int,int> start, pair<int,int> end) {
vector<vector<bool>> blocked(rows, vector<bool>(cols, false));
for (auto& w : walls) blocked[w.first][w.second] = true;
vector<vector<bool>> tr(rows, vector<bool>(cols, false));
for (auto& t : treasures) tr[t.first][t.second] = true;
const int INF = INT_MAX / 2;
vector<vector<int>> dist(rows, vector<int>(cols, INF));
dist[start.first][start.second] = 0;
queue<pair<int,int>> q; q.push(start);
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !blocked[nr][nc] && dist[nr][nc] == INF) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
int D = dist[end.first][end.second];
if (D >= INF) return {-1, 0};
vector<vector<int>> f(rows, vector<int>(cols, -1));
f[start.first][start.second] = tr[start.first][start.second] ? 1 : 0;
vector<vector<pair<int,int>>> layer(D + 1);
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (dist[r][c] <= D) layer[dist[r][c]].push_back({r, c});
for (int d = 1; d <= D; d++) {
for (auto& cell : layer[d]) {
int best = -1;
for (auto& dd : dirs) {
int pr = cell.first + dd[0], pc = cell.second + dd[1];
if (pr >= 0 && pr < rows && pc >= 0 && pc < cols
&& dist[pr][pc] == d - 1 && f[pr][pc] >= 0)
best = max(best, f[pr][pc]);
}
if (best >= 0) f[cell.first][cell.second] = best + (tr[cell.first][cell.second] ? 1 : 0);
}
}
return {D, f[end.first][end.second]};
}Given a string containing a sequence of words separated by whitespace, format it so that each output line is exactly lineLength characters long. Use _ instead of space.
Greedy packing: pack as many words as possible onto each line, separated by at least one underscore.
Even underscore distribution (multi-word lines): distribute extra underscores evenly between words; if they do not divide evenly, the extra underscores are appended to the end of the line.
Single-word lines: center the word — half the padding on the left and the rest on the right; any extra goes to the end.
Hyphenated words: words like "self-inflicted", "pre-approval", "mother-in-law" should be kept on one line if possible. If only the prefix-with-hyphen fits (e.g. "self-"), split the word across lines. Inputs may have whitespace around hyphens ("self - inflicted"); normalize as if there were no whitespace.
Example
"a cat is an animal", 6
→ ["a__cat", "is_an_", "animal"]
"cat is an animal and so is a dog", 12
→ ["cat__is_an_", "animal___and", "so_is_a_dog_"]
"human", 8
→ ["_human__"]
"auto-complete is my go - to", 8
→ ["_auto-__", "complete", "is____my", "_go-to__"]解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理