迷宫脱困难题：二分查找结合 BFS 寻最小参数 k

这是一个典型的带有参数调整的最短路径问题，需要找到满足特定条件的参数k。我们可以使用二分查找结合BFS来解决这个问题。 ```cpp #include <iostream> #include <vector> #include <queue> #include <iomanip> #include <cmath> using namespace std; const double EPS = 1e-8; const int INF = 1e9; struct State { int x, y; double time; State(int x, int y, double time) : x(x), y(y), time(time) {} }; int n, m; int sx, sy, tx, ty; vector<vector<int>> maze; double s; bool is_valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0; } bool check(double k) { vector<vector<double>> dist(n, vector<double>(m, INF)); dist[sx][sy] = 0.0; queue<State> q; q.push(State(sx, sy, 0.0)); int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; while (!q.empty()) { State curr = q.front(); q.pop(); if (abs(curr.time - dist[curr.x][curr.y]) > EPS) continue; for (int i = 0; i < 4; ++i) { int nx = curr.x + dx[i]; int ny = curr.y + dy[i]; if (!is_valid(nx, ny)) continue; double new_time = curr.time; if (i < 2) { // up or down new_time += k; } else { // left or right new_time += 1.0; } if (new_time < dist[nx][ny] - EPS) { dist[nx][ny] = new_time; q.push(State(nx, ny, new_time)); } } } return abs(dist[tx][ty] - s) < EPS; } int main() { cin >> n >> m; cin >> sx >> sy >> tx >> ty; sx--; sy--; tx--; ty--; // convert to 0-based index maze.resize(n, vector<int>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> maze[i][j]; } } cin >> s; double left = 0.0, right = 1e6; double ans = 0.0; while (right - left > EPS) { double mid = (left + right) / 2; if (check(mid)) { ans = mid; right = mid; } else { left = mid; } } cout << fixed << setprecision(3) << ans << endl; return 0; } ``` 1. 二分查找的精度控制很重要，EPS设置为1e-8可以保证足够的精度。 2. BFS实现时需要注意处理浮点数比较的精度问题，使用EPS进行比较。 3. 移动方向的代价计算需要区分上下移动和左右移动，上下移动消耗k秒，左右移动消耗1秒。 ######[AI写代码神器 | 735点数解答 | 2025-07-01 15:27:29]