上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int minimalSteps(vector<string>& maze) {
}
};
python3 解法, 执行用时: 3260 ms, 内存消耗: 44.2 MB, 提交时间: 2023-10-23 17:13:26
from queue import Queue
class Solution:
def minimalSteps(self, maze: List[str]) -> int:
# 四个方向
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
# 计算（x, y）到maze中其他点的距离，结果保存在ret中
def bfs(x, y, maze, m, n):
ret = [[-1]*n for _ in range(m)]
ret[x][y] = 0
q = Queue()
q.put((x,y))
while q.qsize():
curx, cury = q.get()
for dx, dy in dd:
nx = curx + dx
ny = cury + dy
if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] != '#' and ret[nx][ny] == -1:
ret[nx][ny] = ret[curx][cury] + 1
q.put((nx, ny))
return ret
m = len(maze)
n = len(maze[0])
startX = -1
startY = -1
endX = -1
endY = -1
# 机关 & 石头
buttons = []
stones = []
# 记录所有特殊信息的位置
for i in range(m):
for j in range(n):
if maze[i][j] == 'S':
startX = i
startY = j
elif maze[i][j] == 'T':
endX = i
endY = j
elif maze[i][j] == 'O':
stones.append((i,j))
elif maze[i][j] == 'M':
buttons.append((i,j))
else:
pass
nb = len(buttons)
ns = len(stones)
startToAnyPos = bfs(startX, startY, maze, m, n)
# 若没有机关，最短距离就是(startX, startY)到(endX, endY)的距离
if nb == 0:
return startToAnyPos[endX][endY]
# 记录第i个机关到第j个机关的最短距离
# dist[i][nb]表示到起点的距离， dist[i][nb+1]表示到终点的距离
dist = [[-1]*(nb+2) for _ in range(nb)]
# 遍历所有机关，计算其和其他点的距离
buttonsToAnyPos = []
for i in range(nb):
bx, by = buttons[i]
# 记录第i个机关到其他点的距离
iToAnyPos = bfs(bx, by, maze, m, n)
buttonsToAnyPos.append(iToAnyPos)
# 第i个机关到终点的距离就是(bx, by)到(endX, endY)的距离
dist[i][nb + 1] = iToAnyPos[endX][endY]
for i in range(nb):
# 计算第i个机关到(startX, startY)的距离
# 即从第i个机关出发，通过每个石头(sx, sy)，到(startX, startY)的最短距离
tmp = -1
for j in range(ns):
sx, sy = stones[j]
if buttonsToAnyPos[i][sx][sy] != -1 and startToAnyPos[sx][sy] != -1:
if tmp == -1 or tmp > buttonsToAnyPos[i][sx][sy] + startToAnyPos[sx][sy]:
tmp = buttonsToAnyPos[i][sx][sy] + startToAnyPos[sx][sy]
dist[i][nb] = tmp
# 计算第i个机关到第j个机关的距离
# 即从第i个机关出发，通过每个石头(sx, sy)，到第j个机关的最短距离
for j in range(i+1, nb):
mn = -1
for k in range(ns):
sx, sy = stones[k]
if buttonsToAnyPos[i][sx][sy] != -1 and buttonsToAnyPos[j][sx][sy] != -1:
if mn == -1 or mn > buttonsToAnyPos[i][sx][sy] + buttonsToAnyPos[j][sx][sy]:
mn = buttonsToAnyPos[i][sx][sy] + buttonsToAnyPos[j][sx][sy]
# 距离是无向图，对称的
dist[i][j] = mn
dist[j][i] = mn
# 若有任意一个机关 到起点或终点没有路径(即为-1),则说明无法达成，返回-1
for i in range(nb):
if dist[i][nb] == -1 or dist[i][nb+1] == -1:
return -1
# dp数组， -1代表没有遍历到, 1<<nb表示题解中提到的mask, dp[mask][j]表示当前处于第j个机关，总的触发状态为mask所需要的最短路径, 由于有2**nb个状态，因此1<<nb的开销必不可少
dp = [[-1]*nb for _ in range(1 << nb)]
# 初识状态，即从start到第i个机关，此时mask的第i位为1，其余位为0
for i in range(nb):
dp[1 << i][i] = dist[i][nb]
# 二进制中数字大的mask的状态肯定比数字小的mask的状态多，所以直接从小到大遍历更新即可
for mask in range(1, (1 << nb)):
for i in range(nb):
# 若当前位置是正确的，即mask的第i位是1
if mask & (1 << i) != 0:
for j in range(nb):
# 选择下一个机关j,要使得机关j目前没有到达，即mask的第j位是0
if mask & (1 << j) == 0:
nextMask = mask | (1 << j)
if dp[nextMask][j] == -1 or dp[nextMask][j] > dp[mask][i] + dist[i][j]:
dp[nextMask][j] = dp[mask][i] + dist[i][j]
# 最后一个机关到终点
ans = -1
finalMask = (1 << nb) - 1
for i in range(nb):
if ans == -1 or ans > dp[finalMask][i] + dist[i][nb + 1]:
ans = dp[finalMask][i] + dist[i][nb + 1]
return ans
golang 解法, 执行用时: 80 ms, 内存消耗: 12.9 MB, 提交时间: 2023-10-23 17:12:51
var (
dx = []int{1, -1, 0, 0}
dy = []int{0, 0, 1, -1}
n, m int
)
func minimalSteps(maze []string) int {
n, m = len(maze), len(maze[0])
// 机关 & 石头
var buttons, stones [][]int
// 起点 & 终点
sx, sy, tx, ty := -1, -1, -1, -1
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
switch maze[i][j] {
case 'M':
buttons = append(buttons, []int{i, j})
case 'O':
stones = append(stones, []int{i, j})
case 'S':
sx, sy = i, j
case 'T':
tx, ty = i, j
}
}
}
nb, ns := len(buttons), len(stones)
startDist := bfs(sx, sy, maze)
// 边界情况：没有机关
if nb == 0 {
return startDist[tx][ty]
}
// 从某个机关到其他机关 / 起点与终点的最短距离。
dist := make([][]int, nb)
for i := 0; i < nb; i++ {
dist[i] = make([]int, nb + 2)
for j := 0; j < nb + 2; j++ {
dist[i][j] = -1
}
}
// 中间结果
dd := make([][][]int, nb)
for i := 0; i < nb; i++ {
dd[i] = bfs(buttons[i][0], buttons[i][1], maze)
// 从某个点到终点不需要拿石头
dist[i][nb + 1] = dd[i][tx][ty]
}
for i := 0; i < nb; i++ {
tmp := -1
for k := 0; k < ns; k++ {
midX, midY := stones[k][0], stones[k][1]
if dd[i][midX][midY] != -1 && startDist[midX][midY] != -1 {
if tmp == -1 || tmp > dd[i][midX][midY] + startDist[midX][midY] {
tmp = dd[i][midX][midY] + startDist[midX][midY]
}
}
}
dist[i][nb] = tmp
for j := i + 1; j < nb; j++ {
mn := -1
for k := 0; k < ns; k++ {
midX, midY := stones[k][0], stones[k][1]
if dd[i][midX][midY] != -1 && startDist[midX][midY] != -1 {
if mn == -1 || mn > dd[i][midX][midY] + dd[j][midX][midY] {
mn = dd[i][midX][midY] + dd[j][midX][midY]
}
}
}
dist[i][j] = mn
dist[j][i] = mn
}
}
// 无法达成的情形
for i := 0; i < nb; i++ {
if dist[i][nb] == -1 || dist[i][nb + 1] == -1 {
return -1
}
}
// dp 数组， -1 代表没有遍历到
dp := make([][]int, 1 << nb)
for i := 0; i < (1 << nb); i++ {
dp[i] = make([]int, nb)
for j := 0; j < nb; j++ {
dp[i][j] = -1
}
}
for i := 0; i < nb; i++ {
dp[1 << i][i] = dist[i][nb]
}
// 由于更新的状态都比未更新的大，所以直接从小到大遍历即可
for mask := 1; mask < (1 << nb); mask++ {
for i := 0; i < nb; i++ {
// 当前 dp 是合法的
if mask & (1 << i) != 0 {
for j := 0; j < nb; j++ {
// j 不在 mask 里
if mask & (1 << j) == 0 {
next := mask | (1 << j)
if dp[next][j] == -1 || dp[next][j] > dp[mask][i] + dist[i][j] {
dp[next][j] = dp[mask][i] + dist[i][j]
}
}
}
}
}
}
ret := -1
finalMask := (1 << nb) - 1
for i := 0; i < nb; i++ {
if ret == -1 || ret > dp[finalMask][i] + dist[i][nb + 1] {
ret = dp[finalMask][i] + dist[i][nb + 1]
}
}
return ret
}
func bfs(x, y int, maze []string) [][]int {
ret := make([][]int, n)
for i := 0; i < n; i++ {
ret[i] = make([]int, m)
for j := 0; j < m; j++ {
ret[i][j] = -1
}
}
ret[x][y] = 0
queue := [][]int{}
queue = append(queue, []int{x, y})
for len(queue) > 0 {
p := queue[0]
queue = queue[1:]
curx, cury := p[0], p[1]
for k := 0; k < 4; k++ {
nx, ny := curx + dx[k], cury + dy[k]
if inBound(nx, ny) && maze[nx][ny] != '#' && ret[nx][ny] == -1 {
ret[nx][ny] = ret[curx][cury] + 1
queue = append(queue, []int{nx, ny})
}
}
}
return ret
}
func inBound(x, y int) bool {
return x >= 0 && x < n && y >= 0 && y < m
}
java 解法, 执行用时: 78 ms, 内存消耗: 46.2 MB, 提交时间: 2023-10-23 17:12:33
class Solution {
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
int n, m;
public int minimalSteps(String[] maze) {
n = maze.length;
m = maze[0].length();
// 机关 & 石头
List<int[]> buttons = new ArrayList<int[]>();
List<int[]> stones = new ArrayList<int[]>();
// 起点 & 终点
int sx = -1, sy = -1, tx = -1, ty = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i].charAt(j) == 'M') {
buttons.add(new int[]{i, j});
}
if (maze[i].charAt(j) == 'O') {
stones.add(new int[]{i, j});
}
if (maze[i].charAt(j) == 'S') {
sx = i;
sy = j;
}
if (maze[i].charAt(j) == 'T') {
tx = i;
ty = j;
}
}
}
int nb = buttons.size();
int ns = stones.size();
int[][] startDist = bfs(sx, sy, maze);
// 边界情况：没有机关
if (nb == 0) {
return startDist[tx][ty];
}
// 从某个机关到其他机关 / 起点与终点的最短距离。
int[][] dist = new int[nb][nb + 2];
for (int i = 0; i < nb; i++) {
Arrays.fill(dist[i], -1);
}
// 中间结果
int[][][] dd = new int[nb][][];
for (int i = 0; i < nb; i++) {
int[][] d = bfs(buttons.get(i)[0], buttons.get(i)[1], maze);
dd[i] = d;
// 从某个点到终点不需要拿石头
dist[i][nb + 1] = d[tx][ty];
}
for (int i = 0; i < nb; i++) {
int tmp = -1;
for (int k = 0; k < ns; k++) {
int midX = stones.get(k)[0], midY = stones.get(k)[1];
if (dd[i][midX][midY] != -1 && startDist[midX][midY] != -1) {
if (tmp == -1 || tmp > dd[i][midX][midY] + startDist[midX][midY]) {
tmp = dd[i][midX][midY] + startDist[midX][midY];
}
}
}
dist[i][nb] = tmp;
for (int j = i + 1; j < nb; j++) {
int mn = -1;
for (int k = 0; k < ns; k++) {
int midX = stones.get(k)[0], midY = stones.get(k)[1];
if (dd[i][midX][midY] != -1 && dd[j][midX][midY] != -1) {
if (mn == -1 || mn > dd[i][midX][midY] + dd[j][midX][midY]) {
mn = dd[i][midX][midY] + dd[j][midX][midY];
}
}
}
dist[i][j] = mn;
dist[j][i] = mn;
}
}
// 无法达成的情形
for (int i = 0; i < nb; i++) {
if (dist[i][nb] == -1 || dist[i][nb + 1] == -1) {
return -1;
}
}
// dp 数组， -1 代表没有遍历到
int[][] dp = new int[1 << nb][nb];
for (int i = 0; i < 1 << nb; i++) {
Arrays.fill(dp[i], -1);
}
for (int i = 0; i < nb; i++) {
dp[1 << i][i] = dist[i][nb];
}
// 由于更新的状态都比未更新的大，所以直接从小到大遍历即可
for (int mask = 1; mask < (1 << nb); mask++) {
for (int i = 0; i < nb; i++) {
// 当前 dp 是合法的
if ((mask & (1 << i)) != 0) {
for (int j = 0; j < nb; j++) {
// j 不在 mask 里
if ((mask & (1 << j)) == 0) {
int next = mask | (1 << j);
if (dp[next][j] == -1 || dp[next][j] > dp[mask][i] + dist[i][j]) {
dp[next][j] = dp[mask][i] + dist[i][j];
}
}
}
}
}
}
int ret = -1;
int finalMask = (1 << nb) - 1;
for (int i = 0; i < nb; i++) {
if (ret == -1 || ret > dp[finalMask][i] + dist[i][nb + 1]) {
ret = dp[finalMask][i] + dist[i][nb + 1];
}
}
return ret;
}
public int[][] bfs(int x, int y, String[] maze) {
int[][] ret = new int[n][m];
for (int i = 0; i < n; i++) {
Arrays.fill(ret[i], -1);
}
ret[x][y] = 0;
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[]{x, y});
while (!queue.isEmpty()) {
int[] p = queue.poll();
int curx = p[0], cury = p[1];
for (int k = 0; k < 4; k++) {
int nx = curx + dx[k], ny = cury + dy[k];
if (inBound(nx, ny) && maze[nx].charAt(ny) != '#' && ret[nx][ny] == -1) {
ret[nx][ny] = ret[curx][cury] + 1;
queue.offer(new int[]{nx, ny});
}
}
}
return ret;
}
public boolean inBound(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
}
cpp 解法, 执行用时: 260 ms, 内存消耗: 29.8 MB, 提交时间: 2023-10-23 17:12:17
class Solution {
public:
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m;
bool inBound(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
vector<vector<int>> bfs(int x, int y, vector<string>& maze) {
vector<vector<int>> ret(n, vector<int>(m, -1));
ret[x][y] = 0;
queue<pair<int, int>> Q;
Q.push({x, y});
while (!Q.empty()) {
auto p = Q.front();
Q.pop();
int x = p.first, y = p.second;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (inBound(nx, ny) && maze[nx][ny] != '#' && ret[nx][ny] == -1) {
ret[nx][ny] = ret[x][y] + 1;
Q.push({nx, ny});
}
}
}
return ret;
}
int minimalSteps(vector<string>& maze) {
n = maze.size(), m = maze[0].size();
// 机关 & 石头
vector<pair<int, int>> buttons, stones;
// 起点 & 终点
int sx, sy, tx, ty;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'M') {
buttons.push_back({i, j});
}
if (maze[i][j] == 'O') {
stones.push_back({i, j});
}
if (maze[i][j] == 'S') {
sx = i, sy = j;
}
if (maze[i][j] == 'T') {
tx = i, ty = j;
}
}
}
int nb = buttons.size();
int ns = stones.size();
vector<vector<int>> start_dist = bfs(sx, sy, maze);
// 边界情况：没有机关
if (nb == 0) {
return start_dist[tx][ty];
}
// 从某个机关到其他机关 / 起点与终点的最短距离。
vector<vector<int>> dist(nb, vector<int>(nb + 2, -1));
// 中间结果
vector<vector<vector<int>>> dd(nb);
for (int i = 0; i < nb; i++) {
vector<vector<int>> d = bfs(buttons[i].first, buttons[i].second, maze);
dd[i] = d;
// 从某个点到终点不需要拿石头
dist[i][nb + 1] = d[tx][ty];
}
for (int i = 0; i < nb; i++) {
int tmp = -1;
for (int k = 0; k < ns; k++) {
int mid_x = stones[k].first, mid_y = stones[k].second;
if (dd[i][mid_x][mid_y] != -1 && start_dist[mid_x][mid_y] != -1) {
if (tmp == -1 || tmp > dd[i][mid_x][mid_y] + start_dist[mid_x][mid_y]) {
tmp = dd[i][mid_x][mid_y] + start_dist[mid_x][mid_y];
}
}
}
dist[i][nb] = tmp;
for (int j = i + 1; j < nb; j++) {
int mn = -1;
for (int k = 0; k < ns; k++) {
int mid_x = stones[k].first, mid_y = stones[k].second;
if (dd[i][mid_x][mid_y] != -1 && dd[j][mid_x][mid_y] != -1) {
if (mn == -1 || mn > dd[i][mid_x][mid_y] + dd[j][mid_x][mid_y]) {
mn = dd[i][mid_x][mid_y] + dd[j][mid_x][mid_y];
}
}
}
dist[i][j] = mn;
dist[j][i] = mn;
}
}
// 无法达成的情形
for (int i = 0; i < nb; i++) {
if (dist[i][nb] == -1 || dist[i][nb + 1] == -1) return -1;
}
// dp 数组， -1 代表没有遍历到
vector<vector<int>> dp(1 << nb, vector<int>(nb, -1));
for (int i = 0; i < nb; i++) {
dp[1 << i][i] = dist[i][nb];
}
// 由于更新的状态都比未更新的大，所以直接从小到大遍历即可
for (int mask = 1; mask < (1 << nb); mask++) {
for (int i = 0; i < nb; i++) {
// 当前 dp 是合法的
if (mask & (1 << i)) {
for (int j = 0; j < nb; j++) {
// j 不在 mask 里
if (!(mask & (1 << j))) {
int next = mask | (1 << j);
if (dp[next][j] == -1 || dp[next][j] > dp[mask][i] + dist[i][j]) {
dp[next][j] = dp[mask][i] + dist[i][j];
}
}
}
}
}
}
int ret = -1;
int final_mask = (1 << nb) - 1;
for (int i = 0; i < nb; i++) {
if (ret == -1 || ret > dp[final_mask][i] + dist[i][nb + 1]) {
ret = dp[final_mask][i] + dist[i][nb + 1];
}
}
return ret;
}
};
