[LeetCode] 17 surrounding area

subject

Given a two-dimensional matrix, containing 'X' and 'o' (letter O).

Find all areas surrounded by 'X' and fill all 'O' in these areas with 'X'.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the matrix changes to:

X X X X
X X X X
X X X X
X O X X

Explanation:

The enclosed interval does not exist on the boundary, in other words, 'O' on any boundary will not be filled with 'X'. Any 'O' that is not on or connected to the 'O' on the boundary will eventually be filled with 'X'. If two elements are adjacent horizontally or vertically, they are said to be "connected".

thinking

This problem can be basically determined to be the problem of dfs and bfs traversal of graphs. It is explained in the title that the enclosed interval does not exist on the boundary, so we will think that the O on the boundary needs special treatment. As long as the O on the boundary is specially treated, then the remaining O can be replaced by X. The question turns out to be, how to find an O connected with the border, we need to consider the following situations.

X X X X
X O O X
X X O X
X O O X

At this time, O is not replaced. Because it's connected to the boundary. In order to record this state, we replace o in this case with ා as a placeholder. When the search is over, we will replace o with X (o disconnected from the boundary); when ා, we will replace o (o connected with the boundary).

How to find the O connected with the border?

From the boundary, we can do dfs and bfs on the graph. Here is a brief summary of dfs and dfs.

bfs recursion. You can think about how to recursively traverse a sequence in a binary tree. bfs is non recursive. It is usually stored in a queue. dfs recursion. Most commonly used, such as the first order traversal of binary trees. dfs is non recursive. Generally use stack.

So based on the above idea, we have four ways to realize it.

I'm going to list one of them. Just remember that

code

package com.janeroad;


public class test6 {
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++) {
            // Search from edge o
            boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
            if (isEdge && board[i][j] == 'O') {
                dfs(board, i, j);
            }
        }
    }

    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';
            }
        }
    }
}

public 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] = = '#' indicates that it has been searched
        return;
    }
    board[i][j] = '#';
    dfs(board, i - 1, j);
    // upper
    dfs(board, i + 1, j);
    // lower
    dfs(board, i, j - 1);
    // Left
    dfs(board, i, j + 1);
    // right
}

public static void main(String[] args) {
    char[][] board={{'X','X','X','X'},{'X','O','O','X'},{'X','O','X','X'},{'X','X','O','O'}};
    test6 test6=new test6();
    test6.solve(board);
    for(int i=0;i<board.length;i++) {//s.length indicates the number of rows
        System.out.print("{");
        for(int j=0;j<board[i].length;j++) {//s[i].length indicates the number of columns
            System.out.print(board[i][j]+" ");
        }
        System.out.print("}");
        System.out.println();
}
}
}

Tags: Programming

Posted on Tue, 26 May 2020 08:13:48 -0700 by ciciep