【Java】被围绕的区域(DFS)

image description

【Java】被围绕的区域(DFS)

题目描述

给定一个二维的矩阵,包含 'X' 和 'O'(字母 O)。

找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

示例:

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

解题思路

DFS+递归寻找和边界联通的'O',其他的'O‘都替换成'X'

package com.company;

import java.util.Arrays;

public class xxoo {

    public static void main(String[] args){

        xxoo test = new xxoo();
        char[][] xxxooo = {{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
        test.solve(xxxooo);
        System.out.print(Arrays.deepToString(xxxooo));
    }

    public void solve(char[][] board) {
        if(board == null || board.length == 0){
            return;
        }
        // 行
        int m = board.length;
        // 列
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从边缘o开始搜索
                // 判断是否和边界联通
                // boolean这里只要满足以下四个条件之一就说明此时在边界上
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }
        // 把不是'#‘的'O'改成'X'
        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] == '#') {
                    board[i][j] = 'O';
                }
            }
        }

    }
    // dfs找和边界联通的'O'并变成'#',最后不能被'X'替换,并且下一次就不会被搜索
    public static void dfs(char[][] board,int i,int j) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
            // board[i][j] == '#' 说明已经搜索过了.
            return;
        }
        board[i][j] = '#';
        // 上
        dfs(board, i - 1, j);
        // 下
        dfs(board, i + 1, j);
        // 左
        dfs(board, i, j - 1);
        // 右
        dfs(board, i, j + 1);
    }
}
    ArithmeticJia         0         61         Java         0    

David Ramon

ArithmeticJia

www.guanacossj.com

Life is Short,You need Python

Related Posts

You may like these post too

image description

Leetcode【231】Power

##写在最前面: Given an integer, write a function to determine if it is a power of two. Example 1: Input: 1 Output: true Explanation: 20 = 1 Ex

image description

leetcode【53】最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 来源:力扣(LeetCode)

Comments on this post

0 comments

Leave a comment

it’s easy to post a comment

image description
image description
image description
image description
image description
image description
image description
image description
image description

Copyright © 2019.Company name All rights reserved.苏ICP备19007197号