Java Code by BFS, start from edge of board


  • 0
    W
    private int m;
    private int n;
    public void solve(char[][] board) {
        if(board.length == 0) return;
        m = board.length;
        n = board[0].length;
        for(int i = 0 ;i<m;i++){
            fillOne(i,0,board);
            fillOne(i,n-1,board);
        }
        for(int i = 0 ;i<n;i++){
            fillOne(0,i,board);
            fillOne(m-1,i,board);
        }
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(board[i][j] == 'z'){
                    board[i][j] = 'O';
                }
                else if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }
    public void fillOne(int x, int y,char[][] board){
        Stack<int[]> stack = new Stack<>();
        if(board[x][y] == 'O'){
            int[] temp = new int[2];
            temp[0] = x;
            temp[1] = y;
            stack.push(temp);
        }
        while(!stack.isEmpty()){
            int[] temp = stack.pop();
            int i = temp[0];
            int j = temp [1];
            board[i][j] = 'z';
            if(j-1>=0 && board[i][j-1] == 'O'){
                int[] next = new int[2];
                next[0] = i;
                next[1] = j-1;
                stack.push(next);
            }
            if(i+1<m && board[i+1][j] == 'O'){
                int[] next = new int[2];
                next[0] = i+1;
                next[1] = j;
                stack.push(next);
            }
            if(j+1 < n && board[i][j+1] == 'O'){
                int[] next = new int[2];
                next[0] = i;
                next[1] = j+1;
                stack.push(next);
            }
                
            if(i-1>=0 && board[i-1][j] == 'O'){
                int[] next = new int[2];
                next[0] = i-1;
                next[1] = j;
                stack.push(next);
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.