Given a list of words and a maximum line length, format the text so each line is exactly that length. Rules:
Greedy packing: pack as many words as possible onto each line (separated by at least one space).
Extra spaces in multi-word lines: distribute extra spaces evenly between words; if they don't divide evenly, the leftmost gaps get one extra each. Output uses _ instead of space.
Single-word lines: center the word (pad // 2 underscores on the left, the rest on the right). If pad is odd, the extra goes to the right.
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 them as if there were no whitespace.
Example
words = "auto-complete is my go - to", lineLength = 8
→ ["_auto-__", "complete", "is____my", "_go-to__"]
words = "cat is an animal and so is a dog", lineLength = 12
→ ["cat__is__an_", "animal__and_", "so_is_a_dog_"]
words = "human", lineLength = 8
→ "_human__"Constraints
1 ≤ lineLength ≤ 100, total word characters fit within reasonable memory.
解法
规范化连字符两侧空白，贪心装行。若带连字符的词放不下，拆出最长能放下的「前缀-」。用 _ 填充：单词行居中(左侧 = pad/2)，多词行把多余空格均匀分到各间隙，剩余从左开始多分。复杂度 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
split = False
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:])
split = True
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 outclass 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 <regex>
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;
}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]};
}