C++实现矩阵最短路径问题：BFS算法求解

问题描述

给定一个矩阵，其中每个位置的值为0或1。从矩阵的起始位置走到目标位置，每次操作可以进行以下四种操作：

1. 走到相邻位置
2. 改变当前位置的值为1
3. 改变当前位置的值为0

需要使用最少的单位时间走到目标位置，每次操作花费一个单位时间。

C++代码实现

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Position {
    int x;
    int y;
    int time;
    Position(int _x, int _y, int _time) : x(_x), y(_y), time(_time) {}
};

int shortestPath(vector<vector<int>>& matrix, int startX, int startY, int targetX, int targetY) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    vector<vector<int>> visited(rows, vector<int>(cols, 0));
    queue<Position> q;
    q.push(Position(startX, startY, 0));
    visited[startX][startY] = 1;

    while (!q.empty()) {
        Position curPos = q.front();
        q.pop();
        
        if (curPos.x == targetX && curPos.y == targetY) {
            return curPos.time;
        }

        // 走到相邻位置
        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int nextX = curPos.x + dx[i];
            int nextY = curPos.y + dy[i];
            if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols && visited[nextX][nextY] == 0) {
                q.push(Position(nextX, nextY, curPos.time + 1));
                visited[nextX][nextY] = 1;
            }
        }

        // 改变当前位置的值为1
        if (matrix[curPos.x][curPos.y] == 0) {
            matrix[curPos.x][curPos.y] = 1;
            q.push(Position(curPos.x, curPos.y, curPos.time + 1));
        }

        // 改变当前位置的值为0
        if (matrix[curPos.x][curPos.y] == 1) {
            matrix[curPos.x][curPos.y] = 0;
            q.push(Position(curPos.x, curPos.y, curPos.time + 1));
        }
    }

    return -1; // 无法到达目标位置
}

int main() {
    vector<vector<int>> matrix = {
        {0, 0, 1, 0},
        {0, 0, 0, 0},
        {0, 0, 1, 0},
        {0, 1, 0, 0}
    };
    int startX = 0, startY = 0;
    int targetX = 3, targetY = 3;
    int shortestTime = shortestPath(matrix, startX, startY, targetX, targetY);
    cout << 'Shortest time: ' << shortestTime << endl;

    return 0;
}

代码解释

该代码使用BFS（广度优先搜索）算法来求解最短路径。

1. 定义Position结构体: 表示位置，包含x坐标、y坐标和到达该位置的时间。
2. 使用队列q: 存储待访问的位置。
3. 使用二维数组visited: 记录每个位置是否已经访问过。
4. BFS循环:
   • 将起始位置入队，并将其标记为已访问。
   • 循环取出队首位置，如果该位置是目标位置，则返回到达该位置的时间。
   • 否则，先进行四个方向的相邻位置的遍历，如果相邻位置在矩阵范围内且未被访问过，则将其入队并标记为已访问。
   • 接着，判断当前位置的值，如果是0，则将其改为1，并将其入队；如果是1，则将其改为0，并将其入队。
5. 无法到达目标位置: 如果队列为空，表示无法到达目标位置，返回-1。

示例代码

在主函数中，我们定义了一个4x4的矩阵和起始位置和目标位置，然后调用shortestPath函数求解最短时间，并输出结果。

总结

本文介绍了使用C++实现矩阵最短路径问题，并使用BFS算法进行求解。代码简洁易懂，可供学习和参考。