一个饥饿的人被困在了迷宫当中，渴望走出迷宫。 迷宫的大小为 n × m n×m 但很可惜，有很多位置是不能走的。 每一步，你都可以向上下左右移动一次，花费一秒的时间。 但是迷宫被一种魔法包裹，只有移动时间恰好为 s s 秒的人才能走出去。 而你在迷宫中捡到了一个机器，可以帮助你在每一次向上下移动时消耗 k k 秒的时间，而左右走并不会消耗 k k 秒。 那么你能找到一个最小的正实数 k k 使得从起点到终点的最短用时等于 s s 吗？ 数据保证有解

问题重述 我们有一个大小为 n×m 的迷宫，部分位置不可行走。每一步可以向上下左右移动： - 左右移动：消耗 1 秒。 - 上下移动：消耗 k 秒（k 是一个正实数）。 目标是找到一个最小的正实数 k，使得从起点到终点的最短用时恰好等于 s 秒。 解决思路 1. 问题建模：这是一个加权图的最短路径问题，边的权重取决于移动方向（左右为 1，上下为 k）。 2. 二分搜索：因为 k 是一个实数，且我们需要找到最小的 k 满足条件，可以使用二分搜索来逼近答案。 3. Dijkstra 算法：对于每一个候选的 k，用 Dijkstra 算法计算从起点到终点的最短路径时间，判断是否等于 s。 算法步骤 1. 二分搜索范围：k 的最小可能值 > 0，最大可能值可以通过极端情况估计（比如全部上下移动）。 2. 检查 k 的可行性： - 对于当前的 k，用 Dijkstra 计算最短路径时间 t。 - 如果 t == s，记录 k 并尝试更小的 k。 - 如果 t < s，需要增大 k（因为上下移动耗时增加）。 - 如果 t > s，需要减小 k。 3. 精度控制：二分搜索直到 k 的精度满足要求（比如 1e-6）。 代码实现 ```python import heapq def find_min_k(n, m, grid, start, end, s): # Grid: 0 is blocked, 1 is walkable # Start and end are (x, y) tuples left = 1e-6 right = 1e6 # Adjust based on problem constraints ans = right def shortest_time(k): directions = [(0, 1, 1), (0, -1, 1), (1, 0, k), (-1, 0, k)] dist = [[float('inf')] * m for _ in range(n)] x, y = start dist[x][y] = 0 heap = [(0, x, y)] while heap: current_dist, x, y = heapq.heappop(heap) if (x, y) == end: return current_dist if current_dist > dist[x][y]: continue for dx, dy, cost in directions: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1: new_dist = current_dist + cost if new_dist < dist[nx][ny]: dist[nx][ny] = new_dist heapq.heappush(heap, (new_dist, nx, ny)) return float('inf') for _ in range(100): # Enough iterations for precision mid = (left + right) / 2 t = shortest_time(mid) if abs(t - s) < 1e-6: ans = mid right = mid elif t < s: left = mid else: right = mid return ans # Example usage n, m = 3, 3 grid = [ [1, 1, 1], [1, 0, 1], [1, 1, 1] ] start = (0, 0) end = (2, 2) s = 4.0 print(find_min_k(n, m, grid, start, end, s)) ``` 注意事项 1. 二分搜索的精度：需要足够多的迭代次数以确保 k 的精度。 2. Dijkstra 的正确性：确保优先队列正确处理浮点数权重。 3. 边界情况：如果全部左右移动或全部上下移动，k 的取值会极端化。 额外逻辑点 1. 二分搜索的初始范围需要合理设置，避免遗漏可能的 k 值。 2. Dijkstra 算法中优先队列的实现要注意浮点数的比较精度问题。 3. 迷宫的边界和不可行走区域需要正确处理，避免越界或无效移动。 [2025-07-06 15:48:54 | AI写代码神器 | 929点数解答]