c++ 利比亚行动 (libyan)

Question

题目描述
2011年3月16日以来，利比亚爆发的骚乱不断升级，已严重危及到普通民众和各国在利比亚工作的人员的安全。为了尽快救出在利比亚的同胞，根据利比亚的形势，我国政府告诉每个在利比亚的公民，如何行动才能最快地到达安全的地方，然后由我国派出的飞机、轮船、汽车接回国。
假设利比亚的地图可以描述为一个n行m列的长方形，待拯救的同胞小A在1行1列处，安全的目标位置在n行m列处。小A每次只能向相邻的上、下、左、右四个方向移动，即如果小A现在的位置是i行j列，小A的下一步位置将到达上下左右这四个位置之一，当然小A不能移出n行m列的长方形。
利比亚是一个多沙漠且地形复杂的国家，某些位置是很危险的，人不能去。
给出利比亚的地图,请告诉小A从起点(1,1)走到终点(n,m)最快需要多少步呢？。
输入
输入文件libyan.in的第一行有2个正整数n,m (1≤n≤2000，1≤m≤2000)，它们之间以一个空格分隔，表示利比亚的地形可以分为n行m列。
接下来n行,每行m个字符,分别表示地图中该位置的信息。其中：
字符“”表示这个位置是建筑物、河流、有地雷等人无法走到的位置（保证起点终点不是“”）;
小数点“.”表示人可以走到该位置。
输出
输出文件libyan.out只有一行，该行只有一个正整数。表示为小A从起点到终点，最快需要多少步。

数据说明
60%的数据中，1≤n≤100，1≤m≤100；
80%的数据中，1≤n≤250，1≤m≤250；
90%的数据中，1≤n≤500，1≤m≤500；
100%的数据中，1≤n≤2000，1≤m≤2000。
来源：2011宁波竞赛小学组，如果会，请帮忙看一下，如果我认可，给100元红包

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

要解决这个问题，我们可以采用广度优先搜索（BFS）算法，因为BFS能够保证找到最短路径。以下是C++程序的大致框架和关键点：

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for std::pair
#include <fstream>

using namespace std;

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

// 地图数据
char map[MAXN][MAXN];
bool visited[MAXN][MAXN];

// 用于BFS的队列，存储<行，列，步数>
queue<pair<int, int>> q;

// 检查坐标是否有效
bool isValid(int x, int y, int n, int m) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// BFS算法
int bfs(int n, int m, int start_x, int start_y, int end_x, int end_y) {
    q.push({start_x, start_y, 0});
    visited[start_x][start_y] = true;

    while (!q.empty()) {
        auto [x, y, steps] = q.front();
        q.pop();

        if (x == end_x && y == end_y) {
            return steps; // 到达终点
        }

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

            if (isValid(new_x, new_y, n, m) && map[new_x][new_y] == '.' && !visited[new_x][new_y]) {
                visited[new_x][new_y] = true;
                q.push({new_x, new_y, steps + 1});
            }
        }
    }
    return -1; // 如果没有找到路径
}

int main() {
    ifstream fin("libyan.in");
    ofstream fout("libyan.out");

    if (!fin.is_open() || !fout.is_open()) {
        cerr << "File opening error!" << endl;
        return -1;
    }

    int n, m;
    fin >> n >> m;

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

    int result = bfs(n, m, 0, 0, n - 1, m - 1);
    fout << result;

    fin.close();
    fout.close();

    return 0;
}

这段代码提供了一个基本的框架，包括：

• 定义了地图大小和障碍物的检测。
• 实现了BFS算法来找到最短路径。
• 使用了队列来存储待处理的节点和它们的步数。
• 检查了每个节点的四个方向，并确保它们是可访问的且未被访问过。

请注意，这段代码没有进行错误检查，比如输入文件是否正确，或者输出文件是否成功写入。在实际应用中，你可能需要添加更多的错误处理逻辑。此外，这段代码假设输入文件的格式是正确的，并且地图的起点和终点都是可到达的。