网站建设和推广话术,徐州商城网站建设,天门网站网站建设,阜阳网站建设电话题目描述#xff1a;
给你一个 m x n 的矩阵 board #xff0c;由若干字符 X 和 O 组成#xff0c;捕获 所有 被围绕的区域#xff1a;
连接#xff1a;一个单元格与水平或垂直方向上相邻的单元格连接。区域#xff1a;连接所有 O 的单元格来形成一个区域。围绕#x…题目描述
给你一个 m x n 的矩阵 board 由若干字符 X 和 O 组成捕获 所有 被围绕的区域
连接一个单元格与水平或垂直方向上相邻的单元格连接。区域连接所有 O 的单元格来形成一个区域。围绕如果您可以用 X 单元格 连接这个区域并且区域中没有任何单元格位于 board 边缘则该区域被 X 单元格围绕。
通过将输入矩阵 board 中的所有 O 替换为 X 来 捕获被围绕的区域。
示例 1
输入board [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]
输出[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]
解释 在上图中底部的区域没有被捕获因为它在 board 的边缘并且不能被围绕。
示例 2
输入board [[X]]
输出[[X]]
提示
m board.lengthn board[i].length1 m, n 200board[i][j] 为 X 或 O
题目链接
. - 力扣LeetCode
解题主要思路
这题我觉得有两个麻烦第一个麻烦就是不好理解题目啥意思其实题目的意思是除了边边的 O 以及能跟其构成‘连接’的 O其余的全部改成 X。第二个麻烦就是理解完题目的意思后怎么把符合条件的区域 O 和 不符合条件的区域 O 分隔开来其实有个办法就是咱们遍历边边的元素如果有不符合条件的 O边边的 O 以及能跟其构成‘连接’的 O咱们把他改成于 O X 无关的符号譬如 ? 之后二维数组内的所有 O 都是符合条件的 O即需要改为 X 的数组内的所有 ? 都是原本不符合条件的 O 我们需要将其改回来。
解题代码
class Solution {
public:typedef pairint, int PII;int dx[4]{0, 0, 1, -1};int dy[4]{1, -1, 0, 0};int m, n;void solve(vectorvectorchar board) {m board.size(), n board[0].size();// 先将与边缘的‘O‘相连的全部改为’O‘、‘X’无关的符号譬如?for (int i 0; i n; i) { // 第一行和最后一行if (board[0][i] O) bfs(board, 0, i );if (board[m-1][i] O) bfs(board, m-1, i);}for (int j 0; j m; j) { // 第一列和最后一列if (board[j][0] O) bfs(board, j, 0);if (board[j][n-1] O) bfs(board, j, n-1);}// 此时二维数组board里的全部O全部符合题目要求可直接改成Xfor (int i 0; i m; i) {for (int j 0; j n; j) {if (board[i][j] ?) board[i][j] O;else if (board[i][j] O) board[i][j] X;}}}void bfs(vectorvectorchar board, int r, int c){queuePII que;que.push(make_pair(r, c));board[r][c] ?;while (que.size()) {auto [a, b] que.front();que.pop();for (int i 0; i 4; i) {int x a dx[i];int y b dy[i];if (x 0 x m y 0 y n board[x][y] O) {que.push(make_pair(x, y));board[x][y] ?;}}}}
};
