LeetCode – Regiones rodeadas (Java)

Dado un tablero 2D que contiene ‘X’ y ‘O’, capture todas las regiones rodeadas por ‘X’. Una región se captura cambiando todas las «O» por «X» en esa región rodeada.

Por ejemplo,

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

Después de ejecutar su función, la placa debería ser:

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

Análisis

Este problema es similar al Número de islas. En este problema, solo las celdas de los límites no se pueden rodear. Entonces, primero podemos fusionar esas O en los límites como en Número de islas y reemplazar las O con ‘#’, y luego escanear el tablero y reemplazar todas las O que quedan (si las hay).

1. Búsqueda en profundidad

public void solve(char[][] board) {
    if(board == null || board.length==0) 
        return;
 
    int m = board.length;
    int n = board[0].length;
 
    //merge O's on left & right boarder
    for(int i=0;i<m;i++){
        if(board[i][0] == 'O'){
            merge(board, i, 0);
        }
 
        if(board[i][n-1] == 'O'){
            merge(board, i, n-1);
        }
    }
 
    //merge O's on top & bottom boarder
    for(int j=0; j<n; j++){
         if(board[0][j] == 'O'){
            merge(board, 0, j);
        }
 
        if(board[m-1][j] == 'O'){
            merge(board, m-1, j);
        }
    }
 
    //process the board
    for(int i=0;i<m;i++){
        for(int j=0; j<n; j++){
            if(board[i][j] == 'O'){
                board[i][j] = 'X';
            }else if(board[i][j] == '#'){
                board[i][j] = 'O';
            }
        }
    }
}
 
public void merge(char[][] board, int i, int j){
    board[i][j] = '#';
 
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
 
    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'){
            merge(board, x, y);
        }
    }
}

LeetCode - Cruce de órdenes a nivel de árbol binario (Java)

2. Búsqueda de aliento primero

También podemos usar una cola para hacer una búsqueda inicial de este problema.

public void solve(char[][] board) {
    if(board==null || board.length==0 || board[0].length==0)
        return;
 
    int m=board.length;
    int n=board[0].length;
 
 
    for(int j=0; j<n; j++){
        if(board[0][j]=='O'){
            bfs(board, 0, j);
        }
    }
 
    for(int j=0; j<n; j++){
        if(board[m-1][j]=='O'){
            bfs(board, m-1, j);
        }
    }
 
    for(int i=0; i<m; i++){
        if(board[i][0]=='O'){
            bfs(board, i, 0);
        }
    }
 
    for(int i=0; i<m; i++){
        if(board[i][n-1]=='O'){
            bfs(board, i, n-1);
        }
    }
 
    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]=='1'){
                board[i][j]='O';
            }
        }
    }
}
 
public void bfs(char[][] board, int o, int p){
    int m=board.length;
    int n=board[0].length;
 
    int index = o*n+p;
    LinkedList<Integer> queue = new LinkedList<Integer>();
    queue.offer(index);
    board[o][p]='1';
 
    while(!queue.isEmpty()){
        int top = queue.poll();
        int i=top/n;
        int j=top%n;
 
        if(i-1>=0 && board[i-1][j]=='O'){
            board[i-1][j]='1';
            queue.offer((i-1)*n+j);
        }
        if(i+1<m && board[i+1][j]=='O'){
            board[i+1][j]='1';
            queue.offer((i+1)*n+j);
        }
        if(j-1>=0 && board[i][j-1]=='O'){
            board[i][j-1]='1';
            queue.offer(i*n+j-1);
        }
        if(j+1<n && board[i][j+1]=='O'){
            board[i][j+1]='1';
            queue.offer(i*n+j+1);
        }
    }
}

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta