用c++写一个用的dfs算法求出可达矩阵

当然，下面是使用C++编写的基于DFS算法求解可达矩阵的示例代码：

#include <iostream>
#include <vector>

using namespace std;

// 定义矩阵的行数和列数
const int ROW = 5;
const int COL = 5;

// 定义矩阵中的四个方向
const int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// 判断坐标是否有效
bool isValid(int x, int y) {
    return (x >= 0 && x < ROW && y >= 0 && y < COL);
}

// 使用DFS算法求解可达矩阵
void dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int x, int y) {
    visited[x][y] = true;

    // 在四个方向上搜索可达的位置
    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];

        // 如果新位置有效且尚未被访问过，则进行DFS搜索
        if (isValid(nx, ny) && matrix[nx][ny] == 1 && !visited[nx][ny]) {
            dfs(matrix, visited, nx, ny);
        }
    }
}

// 求解可达矩阵
vector<vector<bool>> findReachableMatrix(vector<vector<int>>& matrix) {
    vector<vector<bool>> reachable(ROW, vector<bool>(COL, false));
    vector<vector<bool>> visited(ROW, vector<bool>(COL, false));

    // 遍历矩阵，对每个起始点进行DFS搜索
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (matrix[i][j] == 1 && !visited[i][j]) {
                dfs(matrix, visited, i, j);
            }
        }
    }

    // 根据访问情况更新可达矩阵
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (visited[i][j]) {
                reachable[i][j] = true;
            }
        }
    }

    return reachable;
}

int main() {
    vector<vector<int>> matrix = {{0, 1, 0, 0, 1},
                                  {1, 0, 1, 1, 0},
                                  {0, 1, 0, 1, 0},
                                  {0, 1, 1, 0, 0},
                                  {1, 0, 0, 0, 1}};

    vector<vector<bool>> reachableMatrix = findReachableMatrix(matrix);

    // 输出可达矩阵
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            cout << reachableMatrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

在该代码中，使用了DFS算法来搜索可达矩阵。首先，我们定义了两个辅助函数，`isValid` 用于判断坐标是否有效，`dfs` 用于进行深度优先搜索。然后，在 `findReachableMatrix` 函数中，遍历矩阵，对每个起始点进行DFS搜索。在DFS搜索中，首先将当前位置标记为已访问，然后在四个方向上搜索可达的位置，如果新位置有效且尚未被访问过，则进行DFS搜索。最后，根据访问情况更新可达矩阵。在示例代码中，我们使用一个5x5的矩阵进行演示，你可以根据需要修改矩阵的大小和内容。