题目描述你陷入了一个 n×m 的方形迷宫 你只可以向上 向下 向左或向右移动 其中 # 是墙 不能移动到墙上 是路 你可以在路上移动另外 你还可以花费 1 个金币进行跳跃 比如你当前处于 xy 位置 你可以跳跃到以 xy 为中心的 5×5 的任意非墙位置问你在迷宫中行走 从 x1y1 到达 x2y2 位置 最少需要花费多少枚金币数据格式输入格式第一行两个整数 nm 表示迷宫的行和列第二行是两个整

#include #include #include #include using namespace std;

int n, m; int x1, y1; int x2, y2; vector<vector> maze; vector<vector> cost; vector<vector> visited;

bool isValid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] != '#'; }

int bfs() { queue<pair<int, int>> q; q.push({x1, y1}); cost[x1][y1] = 0; visited[x1][y1] = 1;

while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();

    if (x == x2 && y == y2) {
        return cost[x][y];
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isValid(nx, ny) && !visited[nx][ny]) {
            q.push({nx, ny});
            cost[nx][ny] = cost[x][y];
            visited[nx][ny] = 1;
        }
    }

    for (int i = -2; i <= 2; i++) {
        for (int j = -2; j <= 2; j++) {
            int nx = x + i;
            int ny = y + j;

            if (isValid(nx, ny) && !visited[nx][ny]) {
                q.push({nx, ny});
                cost[nx][ny] = cost[x][y] + 1;
                visited[nx][ny] = 1;
            }
        }
    }
}

return -1;

}

int main() { cin >> n >> m; cin >> x1 >> y1; cin >> x2 >> y2;

maze.resize(n, vector<char>(m));
cost.resize(n, vector<int>(m, INT_MAX));
visited.resize(n, vector<int>(m, 0));

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> maze[i][j];
    }
}

int minCost = bfs();
cout << minCost << endl;

return 0;