首页 > 试题广场 >

被围绕的区域

[编程题]被围绕的区域
  • 热度指数:2197 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个 n*m 大小的的矩阵,矩阵中由 ‘X' 和 'O' 构成,找到所有被 'X' 围绕的区域,并将其用 'X' 填充。

例如:
[['X','X','X','X'],
['X','O','O','X'],
['X','O','X','X'],
['X','X','O','X']]
中间的三个 ‘O’ 被 'X'围绕,因此将其填充为 'X' ,但第四行的 'O' 下方没有被 'X' 围绕,因此不改变,结果为
[['X','X','X','X'],
['X','X','X','X'],
['X','X','X','X'],
['X','X','O','X']]

数据范围: ,矩阵中保证只含有 'X' 和 'O'
示例1

输入

[[X,X,X,X],[X,O,O,X],[X,O,X,X],[X,X,O,X]]

输出

[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,X,O,X]]
示例2

输入

[[O]]

输出

[[O]]

备注:

算法流程

思路很简单,直接用DFS求解
  1. 先遍历整个矩阵的边界,发现边界有O就开始进行深搜,把边界O连通的趋于全部LOCK住(将O改为L)。此时矩阵中剩下的O就是被X所围绕的封闭区域。
  2. 然后双重循环,把矩阵中剩下的O改成X。
  3. 最后把步骤1中锁住的O还原。
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param board char字符型二维数组 
     * @return char字符型二维数组
     */
    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0, 0, -1, 1};
    public char[][] surroundedArea (char[][] board) {
        // 溜边界,先把边界处的O找到,然后锁死它的连通区域
        int n = board.length, m = board[0].length;
        for(int j = 0; j < board[0].length; j++){
            if(board[0][j] == 'O'){
                dfs(board, 0, j);
            }
            if(board[n - 1][j] == 'O'){
                dfs(board, n - 1, j);
            }
        }
        for(int i = 1; i < n - 1; i++){
            if(board[i][0] == 'O'){
                dfs(board, i, 0);
            }
            if(board[i][m - 1] == 'O'){
                dfs(board, i, m - 1);
            }
        }
        // 其他的O就是被围绕的O,将其充填为X
        for(int i = 1; i < n - 1; i++){
            for(int j = 1; j < m - 1; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
        // 把之前锁死的O改回来
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(board[i][j] == 'L'){
                    board[i][j] = 'O';
                }
            }
        }
        return board;
    }
    
    private void dfs(char[][] board, int x, int y) {
        if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'O'){
            return;     // 越界或已经不是O就直接返回
        }
        board[x][y] = 'L';    // LOCKED锁住
        for(int i = 0; i < 4; i++){
            dfs(board, x + dx[i], y + dy[i]);
        }
    }
}

复杂度分析

时间复杂度

  1. DFS:对于某个位置(i,j),逻辑上它会被自己的上下左右调用4次,而实际上只要有一次把O改成L后就再也不会在此处递归展开了(最少调用一次,最多调用4次)。因此某个位置只会有限几次被深搜,该步骤的时间复杂度为O(nm)。
  2. 矩阵遍历:双重循环遍历,时间复杂度为O(nm)。
综合以上两个步骤,算法的整体时间复杂度为O(nm)。

空间复杂度

直接在原始矩阵上进行的修改,因此额外空间复杂度O(1)。

发表于 2021-12-19 18:21:43 回复(3)
from operator import le
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param board char字符型二维数组 
# @return char字符型二维数组
#
class Solution:
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        # write code here
        width = len(board[0])
        height = len(board)

        m = [[0 for i in range(width)] for j in range(height)]

        next_group = 1
        res_gourp = set()

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'X':
                    continue

                # 已经被标记组别
                if m[i][j] < next_group and m[i][j] != 0:
                    continue
                else:
                    res_gourp.add(next_group)
                    # 开始使用dfs标记组别
                    self.dfs(board, i, j, next_group, m)
                    next_group += 1
        
        # 绕圈一周
        for i in range(width):
            if m[0][i] in res_gourp:
                res_gourp.remove(m[0][i])

        for i in range(height):
            if m[i][0] in res_gourp:
                res_gourp.remove(m[i][0])

        for i in range(width):
            if m[height-1][i] in res_gourp:
                res_gourp.remove(m[height-1][i])

        for i in range(height):
            if m[i][width-1] in res_gourp:
                res_gourp.remove(m[i][width-1])

        for i in range(len(board)):
            for j in range(len(board[0])):
                if m[i][j] in res_gourp:
                    board[i][j] = 'X'

        return board

    def dfs(self, board, x,y, now_group, m):
        if board[x][y] == 'X':
            return
        if m[x][y] == now_group:
            return
        m[x][y] = now_group

        if x > 1:
            self.dfs(board, x-1,y,now_group,m)

        if y > 1:
            self.dfs(board, x,y-1,now_group,m)

        if x < len(m) - 1:
            self.dfs(board, x + 1,y,now_group,m)

        if y < len(m[0]) - 1:
            self.dfs(board, x,y + 1,now_group,m)


编辑于 2024-03-23 00:07:47 回复(0)
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
    *
    * 
        * @param board char字符型二维数组 
        * @return char字符型二维数组
    */
    pub fn surroundedArea(&self, board: Vec<Vec<char>>) -> Vec<Vec<char>> {
        // write code here
        use std::iter;
        let mut new_board = Vec::new();
        let n = board[0].len();
        new_board.push(iter::repeat('O').take(n + 2).collect::<Vec<_>>());
        for mut i in board.into_iter() {
            let mut v = vec!['O'];
            v.append(&mut i);
            v.push('O');
            new_board.push(v);
        }
        new_board.push(iter::repeat('O').take(n + 2).collect::<Vec<_>>());
        let mut board = new_board;
        let m = board.len();
        let n = board[0].len();
        let is_valid = |(x, y): (isize, isize)| {
            x >= 0 && y >= 0 && x < m as isize && y < n as isize
        };

        depth_first_traversal(&mut board, (0, 0), &is_valid);
        
        for i in 0 .. m {
            for j in 0 .. n {
                board[i][j] = if board[i][j] == 'O' {'X'} else {board[i][j]};
            }
        }
        for i in 0 .. m {
            for j in 0 .. n {
                board[i][j] = if board[i][j] == 'Z' {'O'} else {board[i][j]};
            }
        }
        // println!("{:?}", board);
        
        board[1 .. m - 1].into_iter().map(|i| i[1 .. n - 1].into_iter().map(|c| *c).collect::<Vec<_>>()).collect::<Vec<Vec<char>>>()
    }
}

fn depth_first_traversal<F>(board: &mut Vec<Vec<char>>, pos: (isize, isize), is_valid: &F) -> () where F: Fn((isize, isize)) -> bool {
    if is_valid(pos) && board[pos.0 as usize][pos.1 as usize] == 'O' {
        board[pos.0 as usize][pos.1 as usize] = 'Z';
        let dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)];
        for dir in dirs.iter() {
            depth_first_traversal(board, (pos.0 + dir.0, pos.1 + dir.1), is_valid);
        }
    }
}

发表于 2023-09-05 09:56:46 回复(0)

思路:递归解题。二重循环遍历矩阵,如果为O那么递归寻找左右上下的O,如果能找到边界,那么该相邻的O均没有被围绕,因此不能填充。如果没有找到边界,说明延申的O均被围绕,需要填充。
初版代码:

import java.util.*;
public class Solution {
    public char[][] surroundedArea (char[][] board) {
        for(int i = 1; i < board.length - 1; ++i) {
            for(int j = 1; j < board[i].length - 1; ++j) {
                judge(board, i, j);
            }
        }
        return board;
    }
    public boolean judge(char[][] board, int i, int j) {
        if(i > 0 && i < board.length - 1 && j > 0 && j < board[i].length - 1 && board[i][j] == 'O') {
            board[i][j] = 'X';
            boolean left = judge(board, i, j + 1);
            boolean right = judge(board, i, j - 1);
            boolean up = judge(board, i + 1, j);
            boolean down = judge(board, i - 1, j);
            if(left && right && up && down) {
                return true;
            }
            board[i][j] = 'O';
            return false;
        } 
        if((i == 0 || i == board.length - 1 || j == 0 || j == board[i].length - 1) && board[i][j] == 'O')
            return false;
        return true;
    }
}

值得注意的是,如果整个矩阵都是O,那么将会重复递归多次,因此可以采用记忆化手段:把没有被围绕的O做上标记,避免下次继续递归。

import java.util.*;
public class Solution {
    public char[][] surroundedArea (char[][] board) {
        boolean dp[][] = new boolean[board.length][board[0].length];
        for(int i = 1; i < board.length - 1; ++i) {
            for(int j = 1; j < board[i].length - 1; ++j) {
                judge(dp, board, i, j);
            }
        }
        return board;
    }
    public boolean judge(boolean [][]dp, char[][] board, int i, int j) {
        if(i > 0 && i < board.length - 1 && j > 0 && j < board[i].length - 1 && board[i][j] == 'O' && !dp[i][j]) {
            board[i][j] = 'X';
            boolean left = judge(dp, board, i, j + 1);
            boolean right = judge(dp, board, i, j - 1);
            boolean up = judge(dp, board, i + 1, j);
            boolean down = judge(dp, board, i - 1, j);
            if(left && right && up && down) {
                return true;
            }
            board[i][j] = 'O';
            dp[i][j] = true;
            return false;
        } 
        if((i == 0 || i == board.length - 1 || j == 0 || j == board[i].length - 1) && board[i][j] == 'O')
            return false;
        return true;
    }
}
发表于 2023-04-17 15:12:19 回复(0)

正着思考从中间搜'O'然后判断是否被包围很麻烦,因此反向思考,直接从边界上的'O'开始,把和边界上的'O'连通的'O'全部标记一遍。最后把没有标记的'O'替换为'X'即可。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param board char字符型二维数组 
     * @return char字符型二维数组
     */
     boolean[][] vis ;
     int row;
     int col;
    public char[][] surroundedArea (char[][] board) {
        // write code here
        row = board.length;
        col = board[0].length;
        boolean[][] flag = new boolean[row][col];
        vis = new boolean[row][col];
        for(int i=0;i<col;i++){
            if(board[0][i] == 'O'){
                dfs(board,0,i);
            }
        }
        for(int i=0;i<row;i++){
            if(board[i][0] == 'O'){
                dfs(board,i,0);
            }
        }
        for(int i=0;i<row;i++){
            if(board[i][col - 1] == 'O'){
                dfs(board,i,col - 1);
            }
        }

        for(int i=0;i<col;i++){
            if(board[row - 1][i] == 'O'){
                dfs(board,row - 1,i);
            }
        }

        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(board[i][j] == 't'){
                    board[i][j] = 'O';
                }
            }
        }
        return board;

    }

    int[] dist = new int[]{0,1,0,-1,0};
    public void dfs(char[][] board,int i,int j){
        vis[i][j] = true;
        board[i][j] = 't';

        for(int k=0;k<=3;k++){
            int new_x = i + dist[k];
            int new_y = j + dist[k + 1];
            if(new_x >= 0 && new_x < row && new_y >= 0 && new_y < col && !vis[new_x][new_y] && board[new_x][new_y] == 'O'){
                dfs(board,new_x,new_y);
            }
        }

    }
}
发表于 2023-03-31 17:29:30 回复(0)
package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param board char字符型二维数组 
 * @return char字符型二维数组
*/
func surroundedArea( board [][]byte ) [][]byte {
    n,m:=len(board),len(board[0])
    var dfs func(int,int)
    dfs=func(i,j int){
        if i<0||i>=n||j<0||j>=m||board[i][j]!='O'{
            return
        }
        board[i][j]='y'
        dfs(i+1,j)
        dfs(i-1,j)
        dfs(i,j+1)
        dfs(i,j-1)
    }
    for i:=0;i<m;i++{
        if board[0][i]=='O'{
            dfs(0,i)
        }
        if board[n-1][i]=='O'{
            dfs(n-1,i)
        }
    }
    for i:=0;i<n;i++{
        if board[i][0]=='O'{
            dfs(i,0)
        }
        if board[i][m-1]=='O'{
            dfs(i,m-1)
        }
    }
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if board[i][j]=='O'{
                board[i][j]='X'
            }
        }
    }
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if board[i][j]=='y'{
                board[i][j]='O'
            }
        }
    }
    return board
}

发表于 2023-03-08 21:01:56 回复(0)
int[] dx = {0,1,0,-1};
    int[] dy = {1,0,-1,0};
    public char[][] surroundedArea (char[][] board) {
        // write code here
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board,i,0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board,i,n-1);
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                dfs(board,0,i);
            }
            if (board[m-1][i] == 'O') {
                dfs(board,m-1,i);
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                if(board[i][j] == 'L'){
                    board[i][j] = 'O';
                }
            }
        }
        return board;
    }
        //dfs方法:深度搜索与每一个边界O字符相邻的O字符区域(对应深度优先算法思想中搜索到底的一条单独的路经)
//,将其改为L字符
    public void dfs(char[][] board,int i,int j){
        board[i][j] = 'L';
        for(int k=0;k<4;k++){
            int x = i+dx[k];
            int y = j+dy[k];
            if(x>=0 && x<board.length && y>=0 && y<board[0].length && board[x][y] == 'O'){
                dfs(board,x,y);
            }
        }
    }

发表于 2023-02-15 17:52:45 回复(0)
BFS内存超限了。。。
package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param board char字符型二维数组 
 * @return char字符型二维数组
*/
func surroundedArea(board [][]byte) [][]byte {
	// write code here
	n := len(board)
	m := len(board[0])

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if board[i][j] == 'O' {
				bfs(&board, i, j, n, m)
			}
		}
	}

	return board
}

func bfs(board *[][]byte, x, y int, n, m int) {
	queue := [][2]int{{x, y}} // 初始化把当前坐标加入队列
	currentO := [][2]int{}

	for len(queue) > 0 {
		front := queue[0]
		currentO = append(currentO, front)
		queue = queue[1:]
		i, j := front[0], front[1]
		(*board)[i][j] = 'T'
		if i-1 >= 0 && (*board)[i-1][j] == 'O' {
			queue = append(queue, [2]int{i - 1, j})
		}
		if i+1 < n && (*board)[i+1][j] == 'O' {
			queue = append(queue, [2]int{i + 1, j})
		}
		if j-1 >= 0 && (*board)[i][j-1] == 'O' {
			queue = append(queue, [2]int{i, j - 1})
		}
		if j+1 < m && (*board)[i][j+1] == 'O' {
			queue = append(queue, [2]int{i, j + 1})
		}
	}
	canChange := true
	for i := 0; i < len(currentO); i++ {
		if currentO[i][0] == 0 || currentO[i][0] == n-1 || currentO[i][1] == 0 || currentO[i][1] == m-1 {
			canChange = false
		}
	}
	if canChange {
		for i := 0; i < len(currentO); i++ {
			(*board)[currentO[i][0]][currentO[i][1]] = 'X'
		}
	} else {
		for i := 0; i < len(currentO); i++ {
			(*board)[currentO[i][0]][currentO[i][1]] = 'O'
		}
	}
}

发表于 2022-09-01 11:49:05 回复(0)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param board char字符型二维数组 
# @return char字符型二维数组
#
class Solution:
    def dfs(self, num, i, j):
        if num[i][j] == 'O':
            num[i][j] = 1
            x1 = [0,0,1,-1]
            y1 = [1,-1,0,0]
            for k in range(4):
                x = x1[k]+i 
                y = y1[k]+j
                if 0 <= x < len(num) and 0 <= y < len(num[0]) and num[x][y] == 'O':
                    self.dfs(num, x, y)
        return num
    
    
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        m = len(board)
        n = len(board[0])
        if m > 2 and n > 2:
            for i in range(m):
                for j in range(n):
                    if i == 0&nbs***bsp;j == 0&nbs***bsp;i == m-1&nbs***bsp;j == n-1:
                        board = self.dfs(board, i, j)
            for i in range(m):
                for j in range(n):
                    if board[i][j] == 1:
                        board[i][j] = 'O'
                    else:
                        board[i][j] = 'X'
            return board
        else:
            return board

发表于 2022-08-25 19:03:15 回复(0)
BFS解法
class Solution:
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        # write code here

        m = len(board)
        n = len(board[0])

        def is_valid(x, y):
            return 0<=x<m and 0<=y<n

        def bfs(i, j, from_sig, to_sig):
            q = []
            q.append((i, j))
            board[i][j] = to_sig
            while q:
                sz = len(q)
                for _ in range(sz):
                    i, j = q.pop(0)
                    for di, dj in [[1,0],[0,1],[-1,0],[0,-1]]:
                        new_i, new_j = i+di, j+dj
                        if is_valid(new_i, new_j) and board[new_i][new_j] == from_sig:
                            q.append((new_i, new_j))
                            board[new_i][new_j] = to_sig

        for i in range(m):
            for j in range(n):
                if (i == 0&nbs***bsp;i == m-1&nbs***bsp;j == 0&nbs***bsp;j == n-1) and board[i][j] == "O":
                    bfs(i, j, "O", "SB")

        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    bfs(i, j, "O", "X")
        for i in range(m):
            for j in range(n):
                if board[i][j] == "SB":
                    bfs(i, j, "SB", "O")
                    
        return board


发表于 2022-06-30 20:35:24 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */
    vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
        // write code here
        //先搜索边界上以及与边界相连的所有圆,标记为*进行保护
        //然后把剩余的圆置为x,最后把所有*恢复成圆
        for(int i=0;i<board.size();i++)//先从边界开始搜索,保护边界上的圆
        {
            searchedge(board, i, 0, true);
            searchedge(board, i, board[0].size()-1, true);
        }
        for(int j=0;j<board[0].size();j++)
        {
            searchedge(board, 0, j, true);
            searchedge(board, board.size()-1, j,true);
        }
        for(int i=1;i<board.size()-1;i++)
        {
            for(int j=1;j<board[0].size()-1;j++)
            {
                searchedge(board, i, j, false);
            }
        }
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if(board[i][j]=='1')
                {
                    board[i][j]='X';
                }
                else
                {
                    board[i][j]='O';
                }
            }
        }
        return board;
    }
    void searchedge(vector<vector<char>> &board,int x,int y,bool edge)
    {
        if(x<0||y<0||x>=board.size()||y>=board[0].size())
        {
            return;
        }
        if(board[x][y]!='X'&&board[x][y]!='O')//访问过
        {
            return;
        }
        if(edge)
        {
            if(board[x][y]=='X')
            {
                board[x][y]='1';//访问标记
            }
            else//'O'
            {
                board[x][y]='*';
                searchedge(board, x+1, y, true);
                searchedge(board, x-1, y, true);
                searchedge(board, x, y+1, true);
                searchedge(board, x, y-1, true);
            }
        }
        else
        {
            board[x][y]='1';//访问标记
        }
    }

};
发表于 2022-06-30 15:43:21 回复(0)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * NC226 被围绕的区域
 */
public class Solution226 {

    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * @param board char字符型二维数组
     * @return char字符型二维数组
     */
    public char[][] surroundedArea(char[][] board) {
        // write code here
        int length1 = board.length;
        int length2 = board[0].length;
        Queue<Integer> queue1 = new LinkedList<>();
        Queue<Integer> queue2 = new LinkedList<>();
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';

                    int num = 0;
                    boolean flag = true;
                    queue1.add(i);
                    stack1.add(i);
                    queue2.add(j);
                    stack2.add(j);

                    while (!queue1.isEmpty()) {
                        int poll1 = queue1.poll();
                        int poll2 = queue2.poll();
                        num++;
                        flag &= poll1 != 0 && poll1 != length1 - 1 && poll2 != 0 && poll2 != length2 - 1;
                        if (poll1 > 0 && board[poll1 - 1][poll2] == 'O') {
                            board[poll1 - 1][poll2] = 'X';
                            queue1.add(poll1 - 1);
                            stack1.add(poll1 - 1);
                            queue2.add(poll2);
                            stack2.add(poll2);
                        }
                        if (poll1 < length1 - 1 && board[poll1 + 1][poll2] == 'O') {
                            board[poll1 + 1][poll2] = 'X';
                            queue1.add(poll1 + 1);
                            stack1.add(poll1 + 1);
                            queue2.add(poll2);
                            stack2.add(poll2);
                        }
                        if (poll2 > 0 && board[poll1][poll2 - 1] == 'O') {
                            board[poll1][poll2 - 1] = 'X';
                            queue1.add(poll1);
                            stack1.add(poll1);
                            queue2.add(poll2 - 1);
                            stack2.add(poll2 - 1);
                        }
                        if (poll2 < length2 - 1 && board[poll1][poll2 + 1] == 'O') {
                            board[poll1][poll2 + 1] = 'X';
                            queue1.add(poll1);
                            stack1.add(poll1);
                            queue2.add(poll2 + 1);
                            stack2.add(poll2 + 1);
                        }
                    }

                    if (flag) {
                        while (num > 0) {
                            num--;
                            stack1.pop();
                            stack2.pop();
                        }
                    }
                }


            }
        }

        while (!stack1.isEmpty()) {
            board[stack1.pop()][stack2.pop()] = 'O';
        }
        return board;
    }


    public char[][] surroundedArea1(char[][] board) {
        // write code here
        int length1 = board.length;
        int length2 = board[0].length;
        for (int i = 0; i < length1; i++) {
            dfs(board, i, 0, length1, length2);
            dfs(board, i, length2 - 1, length1, length2);
        }
        for (int j = 1; j < length2 - 1; j++) {
            dfs(board, 0, j, length1, length2);
            dfs(board, length1 - 1, j, length1, length2);
        }
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'Y') {
                    board[i][j] = 'O';
                }
            }
        }
        return board;
    }

    private void dfs(char[][] board, int i, int j, int length1, int length2) {
        if (i < 0 || i >= length1 || j < 0 || j >= length2 || board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'Y';
        dfs(board, i + 1, j, length1, length2);
        dfs(board, i - 1, j, length1, length2);
        dfs(board, i, j + 1, length1, length2);
        dfs(board, i, j - 1, length1, length2);
    }
}

发表于 2022-05-08 22:59:03 回复(0)
class Solution:
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        # write code here
        m,n=len(board),len(board[0])
        def dfs(i,j):
            if (i<0&nbs***bsp;i>m-1)&nbs***bsp;(j<0&nbs***bsp;j>n-1)&nbs***bsp;board[i][j]!="O":
                return
            if board[i][j]=="O":
                board[i][j]="No"
            dfs(i-1,j)
            dfs(i+1,j)
            dfs(i,j-1)
            dfs(i,j+1)
        for i in range(m):
            dfs(i,0)
            dfs(i,n-1)
        
        for j in range(n):
            dfs(0,j)
            dfs(m-1,j)
        for i in range(m):
            for j in range(n):
                if board[i][j]=="O":
                    board[i][j]="X"
                elif board[i][j]=="No":
                    board[i][j]="O"
        return board
发表于 2022-01-19 07:36:21 回复(0)