一个饥饿的人被困在了迷宫当中，渴望走出迷宫。 迷宫的大小为 n × m n×m 但很可惜，有很多位置是不能走的。 每一步，你都可以向上下左右移动一次，花费一秒的时间。 但是迷宫被一种魔法包裹，只有移动时间恰好为 s s 秒的人才能走出去。 而你在迷宫中捡到了一个机器，可以帮助你在每一次向上下移动时消耗 k k 秒的时间，而左右走并不会消耗 k k 秒。 那么你能找到一个最小的正实数 k k 使得从起点到终点的最短用时等于 s s 吗？ 数据保证有解 输入格式 第一行两个数 n , m n,m 第二行四个数 s x , s y , t x , t y sx,sy,tx,ty。分别表示起点所在行数、列数，终点所在行数、列数。 接下来 n n 行，每行 m m 个数，描述迷宫，其中 0 表示可以走，1 表示不能走。 最后一行一个正实数 s s。 输出格式 输出答案 k k，四舍五入保留 3 位小数。C++

这是一个典型的带有参数调整的最短路径问题，需要找到满足特定条件的参数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秒。 [2025-07-01 15:27:29 | AI写代码神器 | 735点数解答]