LeetCode刷题总结 | 图论1—深度优先搜索广度优先搜索一些简单套模板问题

1.深度优先搜索

1.1 深搜三部曲

1.确认递归函数，参数

void dfs(参数)

通常我们递归的时候，我们递归搜索需要了解哪些参数，其实也可以在写递归函数的时候，发现需要什么参数，再去补充就可以。

一般情况，深搜需要二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。

例如这样：

vector<vector<int>> result; // 保存符合条件的所有路径
vector<int> path; // 起点到终点的路径
void dfs (图，目前搜索的节点)

2.确认终止条件

终止条件很重要，写dfs的时候之所以容易死循环，栈溢出等等这些问题，都是因为终止条件没有想清楚。

if (终止条件) {存放结果;return;
}

终止添加不仅是结束本层递归，同时也是我们收获结果的时候。

另外，其实很多dfs写法，没有写终止条件，其实终止条件写在了，下面dfs递归的逻辑里了，也就是不符合条件，直接不会向下递归。

3.处理目前搜索节点出发的路径

一般这里就是一个for循环的操作，去遍历目前搜索节点所能到的所有节点。

for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果
}

代码模版：

vector<vector<int>> result; // 保存符合条件的所有路径，不一定需要
vector<int> path; // 起点到终点的路径，不一定需要
void dfs (图，目前搜索的节点) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}

1.2 深搜例题

leetcode.cn/problems/all-paths-from-source-to-target/description/" rel="nofollow">深搜例题1：797 所有可能的路径（medium）

给你一个有 n 个节点的有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

思路：dfs标准模板题，详细解析

代码实现：

class Solution {
private:vector<vector<int>> result; // 收集符合条件的路径vector<int> path; // 0节点到终点的路径// x：目前遍历的节点// graph：存当前的图void dfs (vector<vector<int>>& graph, int x) {// 要求从节点 0 到节点 n-1 的路径并输出，所以是 graph.size() - 1if (x == graph.size() - 1) { // 找到符合条件的一条路径result.push_back(path);return;}for (int i = 0; i < graph[x].size(); i++) { // 遍历节点n链接的所有节点path.push_back(graph[x][i]); // 遍历到的节点加入到路径中来dfs(graph, graph[x][i]); // 进入下一层递归path.pop_back(); // 回溯，撤销本节点}}
public:vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {path.push_back(0); // 无论什么路径已经是从0节点出发dfs(graph, 0); // 开始遍历return result;}
};

Summary:

本题是比较基础的深度优先搜索模板题，这种有向图路径问题，最合适使用深搜，当然本题也可以使用广搜，但广搜相对来说就麻烦了一些，需要记录一下路径。
而深搜和广搜都适合解决颜色类的问题，例如岛屿系列，其实都是遍历+标记，所以使用哪种遍历都是可以的。

leetcode.cn/problems/number-of-islands/description/" rel="nofollow">深搜例题2：200 岛屿数量（medium）

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

思路：深搜广搜都合适，这里先用深搜，详细解析

代码实现1（终止条件隐藏在调用时）：

// 版本一 
class Solution {
private:int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 没有访问过的 同时 是陆地的visited[nextx][nexty] = true; dfs(grid, visited, nextx, nexty);} }}
public:int numIslands(vector<vector<char>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false)); int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == '1') { visited[i][j] = true;result++; // 遇到没访问过的陆地，+1dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}return result;}
};

代码实现2（明确终止条件）：

// 版本二
class Solution {
private:int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y] || grid[x][y] == '0') return; // 终止条件：访问过的节点 或者 遇到海水visited[x][y] = true; // 标记访问过for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过dfs(grid, visited, nextx, nexty);}}
public:int numIslands(vector<vector<char>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == '1') {result++; // 遇到没访问过的陆地，+1dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}return result;}
};

Summary：

版本一的写法是：下一个节点是否能合法已经判断完了，只要调用dfs就是可以合法的节点。
版本二的写法是：不管节点是否合法，上来就dfs，然后在终止条件的地方进行判断，不合法再return。

理论上来讲，版本一的效率更高一些，因为避免了没有意义的递归调用，在调用dfs之前，就做合法性判断。但从写法来说，可能版本二更利于理解一些。（不过其实都差不太多）

leetcode.cn/problems/max-area-of-island/description/" rel="nofollow">深搜例题3：695 岛屿的最大面积（medium）

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

思路：依旧是深搜广搜都可以的遍历类题目，这里用深搜。详细解析

代码实现1：

// 版本一
class Solution {
private:int count;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的visited[nextx][nexty] = true;count++;dfs(grid, visited, nextx, nexty);}}}public:int maxAreaOfIsland(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {count = 1;  // 因为dfs处理下一个节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地visited[i][j] = true;dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = max(result, count);}}}return result;}
};

代码实现2：

// 版本二
class Solution {
private:int count;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水visited[x][y] = true; // 标记访问过count++;for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过dfs(grid, visited, nextx, nexty);}}public:int maxAreaOfIsland(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {count = 0; // 因为dfs处理当前节点，所以遇到陆地计数为0，进dfs之后在开始从1计数dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = max(result, count);}}}return result;}
};

版本一，在主函数遇到陆地就计数为1，接下来的相邻陆地都在dfs中计算。
版本二在主函数遇到陆地计数为0，也就是不计数，陆地数量都去dfs里做计算。

leetcode.cn/problems/number-of-enclaves/description/" rel="nofollow">深搜例题4：1020 飞地的数量（medium）

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

思路：遍历问题深搜广搜均可，这里用深搜。关键在于逆向思考—从边界开始dfs能达到的陆地就是可以离开的陆地单元格的数量，将其置0，最后统计地图中1的数量即可。详细解析

代码实现：

class Solution {
private:int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向int count; // 统计符合题目要求的陆地空格数量void dfs(vector<vector<int>>& grid, int x, int y) {grid[x][y] = 0;count++;for (int i = 0; i < 4; i++) { // 向四个方向遍历int nextx = x + dir[i][0];int nexty = y + dir[i][1];// 超过边界if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 不符合条件，不继续遍历if (grid[nextx][nexty] == 0) continue;dfs (grid, nextx, nexty);}return;}public:int numEnclaves(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();// 从左侧边，和右侧边 向中间遍历for (int i = 0; i < n; i++) {if (grid[i][0] == 1) dfs(grid, i, 0);if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);}// 从上边和下边 向中间遍历for (int j = 0; j < m; j++) {if (grid[0][j] == 1) dfs(grid, 0, j);if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);}count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) dfs(grid, i, j);}}return count;}
};

leetcode.cn/problems/surrounded-regions/description/" rel="nofollow">深搜例题5：130 被围绕的区域（medium）

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
在这里插入图片描述
思路：深搜广搜均可，这里用深搜。和上面飞地的数量那一题一样—依然是从四周dfs然后将具有O标记的的格子改为A，最后再遍历整个board将O标记为X，而将A标记为O。详细解析

代码实现：

class Solution {
private:int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向void dfs(vector<vector<char>>& board, int x, int y) {board[x][y] = 'A';for (int i = 0; i < 4; i++) { // 向四个方向遍历int nextx = x + dir[i][0];int nexty = y + dir[i][1];// 超过边界if (nextx < 0 || nextx >= board.size() || nexty < 0 || nexty >= board[0].size()) continue;// 不符合条件，不继续遍历if (board[nextx][nexty] == 'X' || board[nextx][nexty] == 'A') continue;dfs (board, nextx, nexty);}return;}public:void solve(vector<vector<char>>& board) {int n = board.size(), m = board[0].size(); // 步骤一：// 从左侧边，和右侧边 向中间遍历for (int i = 0; i < n; i++) {if (board[i][0] == 'O') dfs(board, i, 0);if (board[i][m - 1] == 'O') dfs(board, i, m - 1);}// 从上边和下边 向中间遍历for (int j = 0; j < m; j++) {if (board[0][j] == 'O') dfs(board, 0, j);if (board[n - 1][j] == 'O') dfs(board, n - 1, j);}// 步骤二：for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (board[i][j] == 'O') board[i][j] = 'X';if (board[i][j] == 'A') board[i][j] = 'O';}}}
};

2.广度优先搜索

2.1 广搜模版

广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。
当然，也有一些问题是广搜和深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。

这一圈一圈的搜索过程是怎么做到的，是放在什么容器里，才能这样去遍历。很多网上的资料都是直接说用队列来实现。

其实，我们仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。

用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。
如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。因为栈是先进后出，加入元素和弹出元素的顺序改变了。

那么广搜需要注意转圈搜索的顺序吗？不需要！

所以用队列，还是用栈都是可以的，但大家都习惯用队列了，所以下面的模版用也用队列实现，只不过要明确一下，并不是非要用队列，用栈也可以。

针对四方格地图的代码模版如下：

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素int curx = cur.first;int cury = cur.second; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问}}}
}

2.2 广搜例题

leetcode.cn/problems/number-of-islands/description/" rel="nofollow">广搜例题1：200 岛屿数量（medium）

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

思路：深搜广搜都合适，这里用广搜，可以直接套用模版，只需要在if条件判断是增加一个grid[nextx][nexty] == '1'的条件即可。详细解析

代码实现：

class Solution {
private:
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true; // 只要加入队列，立刻标记while(!que.empty()) {pair<int ,int> cur = que.front(); que.pop();int curx = cur.first;int cury = cur.second;for (int i = 0; i < 4; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {que.push({nextx, nexty});visited[nextx][nexty] = true; // 只要加入队列立刻标记}}}
}
public:int numIslands(vector<vector<char>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == '1') {result++; // 遇到没访问过的陆地，+1bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}return result;}
};

leetcode.cn/problems/max-area-of-island/description/" rel="nofollow">广搜例题2：695 岛屿的最大面积（medium）

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

思路：依旧是深搜广搜都可以的遍历类题目，这里用广搜。详细解析

代码实现：

class Solution {
private:int count;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<int> que;que.push(x);que.push(y);visited[x][y] = true; // 加入队列就意味节点是陆地可到达的点count++;while(!que.empty()) {int xx = que.front();que.pop();int yy = que.front();que.pop();for (int i = 0 ;i < 4; i++) {int nextx = xx + dir[i][0];int nexty = yy + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 节点没有被访问过且是陆地visited[nextx][nexty] = true;count++;que.push(nextx);que.push(nexty);}}}}public:int maxAreaOfIsland(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == 1) {count = 0;bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = max(result, count);}}}return result;}
};

依旧是非常模板，只不过是设置queue装载数据类型的时候换了种当时，本质上没啥区别

leetcode.cn/problems/number-of-enclaves/description/" rel="nofollow">广搜例题3：1020 飞地的数量（medium）

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

思路：遍历问题深搜广搜均可，这里用广搜。关键在于逆向思考—从边界开始bfs能达到的陆地就是可以离开的陆地单元格的数量，将其置0，最后统计地图中1的数量即可。详细解析

代码实现：

class Solution {
private:
int count = 0;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector<vector<int>>& grid, int x, int y) {queue<pair<int, int>> que;que.push({x, y});grid[x][y] = 0; // 只要加入队列，立刻标记count++;while(!que.empty()) {pair<int ,int> cur = que.front(); que.pop();int curx = cur.first;int cury = cur.second;for (int i = 0; i < 4; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过if (grid[nextx][nexty] == 1) {que.push({nextx, nexty});count++;grid[nextx][nexty] = 0; // 只要加入队列立刻标记}}}}public:int numEnclaves(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();// 从左侧边，和右侧边 向中间遍历for (int i = 0; i < n; i++) {if (grid[i][0] == 1) bfs(grid, i, 0);if (grid[i][m - 1] == 1) bfs(grid, i, m - 1);}// 从上边和下边 向中间遍历for (int j = 0; j < m; j++) {if (grid[0][j] == 1) bfs(grid, 0, j);if (grid[n - 1][j] == 1) bfs(grid, n - 1, j);}count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) bfs(grid, i, j);}}return count;}
};

leetcode.cn/problems/surrounded-regions/description/" rel="nofollow">广搜例题4：130 被围绕的区域（medium）

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
在这里插入图片描述
思路：深搜广搜均可，这里用广搜。和上面飞地的数量那一题一样—依然是从四周bfs然后将具有O标记的的格子改为A，最后再遍历整个board将O标记为X，而将A标记为O。详细解析

代码实现：

class Solution {
private:int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 保存四个方向void bfs(vector<vector<char>>& board, int x, int y) {board[x][y] = 'A';queue<int> que;que.push(x);que.push(y);while(!que.empty()) {   int xx = que.front(); que.pop();int yy = que.front(); que.pop();     for (int i = 0; i < 4; i++) { // 向四个方向遍历int nextx = x + dir[i][0];int nexty = y + dir[i][1];// 超过边界if (nextx < 0 || nextx >= board.size() || nexty < 0 || nexty >= board[0].size()) continue;// 不符合条件，不继续遍历if (board[nextx][nexty] == 'O') {que.push(nextx);que.push(nexty);bfs(board, nextx, nexty);}}}return;}public:void solve(vector<vector<char>>& board) {int n = board.size(), m = board[0].size(); // 步骤一：// 从左侧边，和右侧边 向中间遍历for (int i = 0; i < n; i++) {if (board[i][0] == 'O') bfs(board, i, 0);if (board[i][m - 1] == 'O') bfs(board, i, m - 1);}// 从上边和下边 向中间遍历for (int j = 0; j < m; j++) {if (board[0][j] == 'O') bfs(board, 0, j);if (board[n - 1][j] == 'O') bfs(board, n - 1, j);}// 步骤二：for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (board[i][j] == 'O') board[i][j] = 'X';if (board[i][j] == 'A') board[i][j] = 'O';}}}
};