surrounded-regions

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an <code>m x n</code> matrix <code>board</code> containing letters <code>&#39;X&#39;</code> and <code>&#39;O&#39;</code>, capture regions that are surrounded:

<ul>
	<li>Connect: A cell is connected to adjacent cells horizontally or vertically.</li>
	<li>Region: To form a region connect every <code>&#39;O&#39;</code> cell.</li>
	<li>Surround: The region is surrounded with <code>&#39;X&#39;</code> cells if you can connect the region with <code>&#39;X&#39;</code> cells and none of the region cells are on the edge of the <code>board</code>.</li>
</ul>

To capture a surrounded region, replace all <code>&#39;O&#39;</code>s with <code>&#39;X&#39;</code>s in-place within the original board. You do not need to return anything.

&nbsp;
Example 1:

<div class="example-block">
Input: board = [[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;O&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;O&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;X&quot;,&quot;X&quot;]]

Output: [[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;X&quot;,&quot;X&quot;]]

Explanation:
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/xogrid.jpg" style="width: 367px; height: 158px;" />
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.
</div>

Example 2:

<div class="example-block">
Input: board = [[&quot;X&quot;]]

Output: [[&quot;X&quot;]]
</div>

&nbsp;
Constraints:

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>board[i][j]</code> is <code>&#39;X&#39;</code> or <code>&#39;O&#39;</code>.</li>
</ul>

solve

Surrounded Regions

Number of Islands

number-of-islands

岛屿数量

Walls and Gates

walls-and-gates

墙与门

Depth-First Search

Breadth-First Search

Union Find

Array

Matrix

给你一个 <code>m x n</code> 的矩阵 <code>board</code> ，由若干字符 <code>'X'</code> 和 <code>'O'</code>&nbsp;组成，捕获 所有 被围绕的区域：

<ul>
	<li>连接：一个单元格与水平或垂直方向上相邻的单元格连接。</li>
	<li>区域：连接所有&nbsp;<code>'O'</code>&nbsp;的单元格来形成一个区域。</li>
	<li>围绕：如果您可以用&nbsp;<code>'X'</code>&nbsp;单元格 连接这个区域，并且区域中没有任何单元格位于&nbsp;<code>board</code> 边缘，则该区域被 <code>'X'</code>&nbsp;单元格围绕。</li>
</ul>

通过 原地&nbsp;将输入矩阵中的所有 <code>'O'</code>&nbsp;替换为 <code>'X'</code> 来 捕获被围绕的区域。你不需要返回任何值。

<div class="original__bRMd">
<div>
&nbsp;

示例 1：

<div class="example-block">
输入：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"]]

解释：
<img alt="" src="https://pic.leetcode.cn/1718167191-XNjUTG-image.png" style="width: 367px; height: 158px;" />
在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。
</div>

示例 2：

<div class="example-block">
输入：board = [["X"]]

输出：[["X"]]
</div>

&nbsp;

提示：

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>board[i][j]</code> 为 <code>'X'</code> 或 <code>'O'</code></li>
</ul>
</div>
</div>