当前位置：首页 > web >正文

leetcode0130. 被围绕的区域- medium

web 2025/7/14 20:21:19

1 题目：被围绕的区域

官方标定难度：中

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获所有被围绕的区域：

连接：一个单元格与水平或垂直方向上相邻的单元格连接。
区域：连接所有 ‘O’ 的单元格来形成一个区域。
围绕：如果您可以用 ‘X’ 单元格连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 ‘X’ 单元格围绕。
通过原地将输入矩阵中的所有 ‘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.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 ‘X’ 或 ‘O’

2 solution

先把四周没有被围住的部分标记一下，然后将剩下的部分修改过来即可

代码

class Solution {
public:
void solve(int *dr, int *dc, int r, int c, vector<vector<char>> &board) {board[r][c] = 'Y';for (int i = 0; i < 4; i++) {int rr = dr[i] + r;int cc = dc[i] + c;if(rr >= 0 && rr < board.size() && cc >= 0 && cc < board[0].size() && board[rr][cc] == 'O'){solve(dr, dc, rr, cc, board);}}
}void solve(vector<vector<char>> &board) {int dr[] = {0, 1, -1, 0};int dc[] = {1, 0, 0, -1};for(int i = 0; i < board.size(); i++){if(board[i][0] == 'O') solve(dr, dc, i, 0, board);if(board[i][board[0].size() - 1] == 'O') solve(dr, dc, i, board[0].size() - 1, board);}for(int j = 0; j < board[0].size(); j++){if(board[0][j] == 'O') solve(dr, dc, 0, j, board);if(board[board.size() - 1][j] == 'O') solve(dr, dc, board.size() - 1, j, board);}for (auto &row: board) {for (auto &c: row) {if (c == 'Y') c = 'O';else if (c == 'O') c = 'X';}}
}};