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__"]解法
用正则 \s*-\s* → - 规范化连字符。贪心装行；带连字符的词放不下时，尝试最长能装下的 parts[0..k] + '-'。成行后填充：单词行居中；多词行从左到右把多余空格均分到间隙(剩余补到行尾)。复杂度 O(N)(按总字符数)。
import re
def justify(text, L):
text = re.sub(r'\s*-\s*', '-', text)
words = text.split()
lines = []
cur, cur_len = [], 0
i = 0
while i < len(words):
w = words[i]
need = len(w) + (1 if cur else 0)
if cur_len + need <= L:
cur.append(w)
cur_len += need
i += 1
continue
if '-' in w:
parts = w.split('-')
best_prefix = ''
best_k = -1
for k in range(len(parts) - 1):
cand = '-'.join(parts[:k+1]) + '-'
ext = len(cand) + (1 if cur else 0)
if cur_len + ext <= L:
best_prefix, best_k = cand, k
if best_prefix:
cur.append(best_prefix)
words[i] = '-'.join(parts[best_k+1:])
lines.append(cur)
cur, cur_len = [], 0
if cur:
lines.append(cur)
out = []
for line in lines:
word_len = sum(len(w) for w in line)
pad = L - word_len
if len(line) == 1:
left = pad // 2
out.append('_' * left + line[0] + '_' * (pad - left))
else:
gaps = len(line) - 1
base, extra = divmod(pad, gaps)
s = ''
for j, w in enumerate(line):
s += w
if j < gaps:
s += '_' * (base + (1 if j < extra else 0))
out.append(s)
return outimport java.util.*;
class Solution {
public List<String> justify(String text, int L) {
text = text.replaceAll("\\s*-\\s*", "-");
List<String> words = new ArrayList<>(Arrays.asList(text.trim().split("\\s+")));
List<List<String>> lines = new ArrayList<>();
List<String> cur = new ArrayList<>();
int curLen = 0, i = 0;
while (i < words.size()) {
String w = words.get(i);
int need = w.length() + (cur.isEmpty() ? 0 : 1);
if (curLen + need <= L) {
cur.add(w); curLen += need; i++; continue;
}
if (w.contains("-")) {
String[] parts = w.split("-");
String bestPrefix = "";
int bestK = -1;
StringBuilder sb = new StringBuilder();
for (int k = 0; k < parts.length - 1; k++) {
if (k > 0) sb.append('-');
sb.append(parts[k]);
String cand = sb.toString() + "-";
int ext = cand.length() + (cur.isEmpty() ? 0 : 1);
if (curLen + ext <= L) { bestPrefix = cand; bestK = k; }
}
if (!bestPrefix.isEmpty()) {
cur.add(bestPrefix);
StringBuilder rem = new StringBuilder();
for (int k = bestK + 1; k < parts.length; k++) {
if (k > bestK + 1) rem.append('-');
rem.append(parts[k]);
}
words.set(i, rem.toString());
}
}
lines.add(new ArrayList<>(cur));
cur.clear(); curLen = 0;
}
if (!cur.isEmpty()) lines.add(cur);
List<String> out = new ArrayList<>();
for (List<String> line : lines) {
int wordLen = 0;
for (String w : line) wordLen += w.length();
int pad = L - wordLen;
StringBuilder s = new StringBuilder();
if (line.size() == 1) {
int left = pad / 2;
for (int k = 0; k < left; k++) s.append('_');
s.append(line.get(0));
for (int k = 0; k < pad - left; k++) s.append('_');
} else {
int gaps = line.size() - 1;
int base = pad / gaps, extra = pad % gaps;
for (int j = 0; j < line.size(); j++) {
s.append(line.get(j));
if (j < gaps) {
int sp = base + (j < extra ? 1 : 0);
for (int k = 0; k < sp; k++) s.append('_');
}
}
}
out.add(s.toString());
}
return out;
}
}#include <bits/stdc++.h>
#include <regex>
using namespace std;
vector<string> justify(string text, int L) {
text = regex_replace(text, regex("\\s*-\\s*"), "-");
vector<string> words;
stringstream ss(text);
string token;
while (ss >> token) words.push_back(token);
vector<vector<string>> lines;
vector<string> cur;
int curLen = 0;
size_t i = 0;
while (i < words.size()) {
string w = words[i];
int need = w.size() + (cur.empty() ? 0 : 1);
if (curLen + need <= L) {
cur.push_back(w);
curLen += need;
i++;
continue;
}
if (w.find('-') != string::npos) {
vector<string> parts;
size_t l = 0;
while (l <= w.size()) {
size_t r = w.find('-', l);
parts.push_back(w.substr(l, r == string::npos ? string::npos : r - l));
if (r == string::npos) break;
l = r + 1;
}
string bestPrefix;
int bestK = -1;
string acc;
for (size_t k = 0; k + 1 < parts.size(); k++) {
if (k > 0) acc += '-';
acc += parts[k];
string cand = acc + "-";
int ext = cand.size() + (cur.empty() ? 0 : 1);
if (curLen + ext <= L) { bestPrefix = cand; bestK = k; }
}
if (!bestPrefix.empty()) {
cur.push_back(bestPrefix);
string rem;
for (size_t k = bestK + 1; k < parts.size(); k++) {
if (k > (size_t)bestK + 1) rem += '-';
rem += parts[k];
}
words[i] = rem;
}
}
lines.push_back(cur);
cur.clear();
curLen = 0;
}
if (!cur.empty()) lines.push_back(cur);
vector<string> out;
for (auto& line : lines) {
int wordLen = 0;
for (auto& w : line) wordLen += w.size();
int pad = L - wordLen;
string s;
if (line.size() == 1) {
int left = pad / 2;
s += string(left, '_') + line[0] + string(pad - left, '_');
} else {
int gaps = line.size() - 1;
int base = pad / gaps, extra = pad % gaps;
for (size_t j = 0; j < line.size(); j++) {
s += line[j];
if ((int)j < gaps) {
int sp = base + ((int)j < extra ? 1 : 0);
s += string(sp, '_');
}
}
}
out.push_back(s);
}
return out;
}