题目描述 样例
哈密顿路径 旅行商问题
$\color{red}{具体的这题对我来说太难了 ~日后再研究吧}$
----------
算法1
(状态压缩DP?) $O(!)$
时间复杂度
参考文献
真:C++ 代码
没做出来 放弃了
假:c++代码_AC
/*
大概思路：具体的还请看代码里面的注释
把点分为两种，一个列表放石头的，一个列表放机关的
然后求出每个机关到每个石头的距离
然后在求得每个机关到每个机关的距离
然后就是逆天的游戏理解
把一个数的二进制表示当前机关触发的状态
这个数的二进制第i位如果为0就表示第i个机关还没有被触发，反之为1就表示被触发了
然后再找出机关触发状态下，最短的距离
*/
class Solution {
public int minimalSteps(String[] maze) {
int n = maze.length;
char[][] mat = new char[n][];
for (int i = 0; i < n; i++) {
mat[i] = maze[i].toCharArray();
}
int m = mat[0].length;
List<int[]> triggers = new ArrayList<>();
List<int[]> stones = new ArrayList<>();
int[] start = null;
int[] end = null;
//把各个类型的点分开
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 'M') {
triggers.add(new int[]{i, j});
}
if (mat[i][j] == 'O') {
stones.add(new int[]{i, j});
}
if (mat[i][j] == 'S') {
start = new int[]{i, j};
}
if (mat[i][j] == 'T') {
end = new int[]{i, j};
}
}
}
//把初始点加入机关队列，把终点加入石头队列
triggers.add(start);
stones.add(end);
int T = triggers.size();
int S = stones.size();
int[][] dist = new int[T][S];
//方向
int[][] dirs = new int[][]{
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};
//BFS（如果这里不懂得话，不建议先看这道题，先看一下BFS类型得题）
int inf = (int) 1e8;
Deque<int[]> dq = new ArrayDeque<>(n * m);
int[][] access = new int[n][m];
for (int i = 0; i < T; i++) {
dq.clear();
for (int[] a : access) {
Arrays.fill(a, -1);
}
int[] t = triggers.get(i);
access[t[0]][t[1]] = 0;
dq.addLast(t);
while (!dq.isEmpty()) {
int[] head = dq.removeFirst();
for (int[] dir : dirs) {
int x = head[0] + dir[0];
int y = head[1] + dir[1];
if (x < 0 || x >= n || y < 0 || y >= m || mat[x][y] == '#' ||
access[x][y] != -1) {
continue;
}
access[x][y] = access[head[0]][head[1]] + 1;
dq.addLast(new int[]{x, y});
}
}
//dist[i][j]这里就是 第i个机关到第j个机关的最短距离
for (int j = 0; j < S; j++) {
int[] s = stones.get(j);
if (access[s[0]][s[1]] == -1) {
dist[i][j] = inf;
} else {
dist[i][j] = access[s[0]][s[1]];
}
}
}
//循环所有的点，找到最小的移动点
int[][] move = new int[T][T];
for (int i = 0; i < T; i++) {
for (int j = 0; j < T; j++) {
if (i == j) {
continue;
}
move[i][j] = inf;
//石堆的最后一个是终点，所以要-1
for (int k = 0; k < S - 1; k++) {
//i到j的最短距离为：i到k石堆+j到k石堆
move[i][j] = Math.min(move[i][j], dist[i][k] + dist[j][k]);
}
}
}
//初始化
//mask的二进制中，第j位如果为0，证明第j个机关没有触发
int mask = (1 << (T - 1)) - 1;
int[][] dp = new int[T][mask + 1];
for (int i = 0; i < T; i++) {
dp[i][0] = inf;
}
//这里运用二进制，i的第j位如果是0的话，证明第j个机关还没触发，反之，就是第j个机关触发了
dp[T - 1][0] = 0;
for (int i = 1; i <= mask; i++) {
for (int j = 0; j < T; j++) {
dp[j][i] = inf;
//这里相当于剪枝操作吧，如果都是i>>j的最后一位不能触发，就直接过吧
//既然有不能触发的机关，求出就没有意义
if (bit(i, j) == 0) {
continue;
}
//这里异运算，就是找没触发的
//也就是需要改变的状态
int remove = i ^ (1 << j);
for (int k = 0; k < T; k++) {
//当前的j个机关最小值，就是k个机关的remove状态，然后加上k到j的路径
dp[j][i] = Math.min(dp[j][i], dp[k][remove] + move[k][j]);
}
}
}
int ans = inf;
if (T > 1) {
for (int i = 0; i < T - 1; i++) {
//找mask就是全都为1，证明全部机关触发
//dist是上面求得最短距离，第i个机关到s-1的最短路径（到终点的最短路径）
//因为开始的时候，把初始点加入到了机关队列，把终点加入到了石头队列
ans = Math.min(ans, dp[i][mask] + dist[i][S - 1]);
}
} else {
ans = dist[0][S - 1];
}
if (ans >= inf) {
return -1;
}
return ans;
}
int bit(int x, int i) {
return (x >> i) & 1;
}
}
哈密顿路径 过47个样例 最后一个不过
class Solution:
def minimalSteps(self, maze) -> int:
def bfs(a, b):
vis = [[False for _ in range(m)] for _ in range(n)]
s = []
s.append(a)
vis[a[0]][a[1]] = True
step = 0
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
while s:
t = []
for x in s:
for d in dirs:
_x = x[0] + d[0]
_y = x[1] + d[1]
if _x == b[0] and _y == b[1]:
return step + 1
if _x >= 0 and _x < n and _y >= 0 and _y < m and not vis[_x][_y] and maze[_x][_y] != '#':
t.append([_x, _y])
vis[_x][_y] = True
step += 1
s = t
return float("inf")
M = []
O = []
S = None
E = None
n = len(maze)
m = len(maze[0])
for i in range(len(maze)):
for j in range(len(maze[i])):
if maze[i][j] == 'O':
O.append([i, j])
if maze[i][j] == "M":
M.append([i, j])
if maze[i][j] == "S":
S = [i, j]
if maze[i][j] == "T":
E = [i, j]
if len(M) == 0:
tt = bfs(S, E)
if tt == float('inf'):
return -1
else:
return tt
dis = [[0 for _ in range(len(M))] for _ in range(len(O))]
for i in range(len(O)):
for j in range(len(M)):
dis[i][j] = bfs(O[i], M[j])
ddd = [[float('inf') for _ in range(len(M))] for _ in range(len(M))]
for i in range(len(M)):
for j in range(len(M)):
for k in range(len(O)):
ddd[i][j] = min(dis[k][i] + dis[k][j], ddd[i][j])
dis_st = [float('inf') for _ in range(len(O))]
for i in range(len(O)):
dis_st[i] = bfs(S, O[i])
dis_en = [float('inf') for _ in range(len(M))]
for i in range(len(M)):
dis_en[i] = bfs(E, M[i])
dis_all = [[float('inf') for _ in range(len(M) + 2)] for _ in range(len(M) + 2)]
for i in range(1, len(M) + 1):
for j in range(len(O)):
dis_all[0][i] = min(dis_all[0][i], dis_st[j] + dis[j][i-1])
for i in range(1, len(M) + 1):
for j in range(1, len(M) + 1):
dis_all[i][j] = ddd[i - 1][j - 1]
for i in range(1, len(M) + 1):
dis_all[i][len(M) + 1] = dis_en[i - 1]
for i in range(len(M) + 2):
dis_all[i][i] = 0
dp = [[float('inf') for _ in range(len(M) + 2)] for _ in range(1 << (len(M) + 2))]
dp[1][0] = 0
for i in range(1, 1 << (len(M) + 2)):
for j in range(len(M) + 2):
if (i >> j) & 1:
for k in range(len(M) + 2):
if ((i ^ (1 << j)) >> k) & 1:
dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + dis_all[k][j]);
if dp[-1][-1] == float("inf"):
return -1
else:
return dp[-1][-1]
