BFS time exceeded


  • 1
    S
    public class Solution {
    
    public static final int[][] direction = new int[][]{new int[]{-1,0},new int[]{1,0},new int[]{0,-1},new int[]{0,1}};
    
    
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        
        for (int i = 0; i < board.length; i++){
            if (board[i][0] == 'O') bfs(board,i,0);
            if (board[i][board[0].length-1] == 'O') bfs(board,i,board[0].length-1);
        }
        for (int j = 0; j < board[0].length; j++){
            if (board[0][j] == 'O') bfs(board,0,j);
            if (board[board.length-1][j] == 'O') bfs(board,board.length-1,j);
        }
        
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else if (board[i][j] == '#'){
                    board[i][j] = 'O';
                }
            }
        }
        
        
    }
    
    public void bfs(char[][] board, int x, int y){
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y] == 'X' || board[x][y] == '#') return;
        Queue<Integer> queue = new LinkedList<>();
        int col = board[0].length;
        queue.offer(x*col+y);
        while (!queue.isEmpty()){
            int cur = queue.poll();
            int curX = cur/col, curY = cur%col;
    
            // p1 :  bound condition check here is ok
            if (curX < 0 || curY < 0 || curX >= board.length || curY >= board[0].length || board[curX][curY] != 'O')  continue; 
    
            board[curX][curY] = '#';
            for (int[] dir: direction){
                int nextX = dir[0] + curX;
                int nextY = dir[1] + curY;
    
                // p2:  bound condition check here will get timeout
                // if (nextX < 0 || nextY < 0 || nextX >= board.length || nextY >= board[0].length) continue;
                // if (board[nextX][nextY] == 'X' || board[nextX][nextY] == '#') continue;
    
                queue.offer(nextX*col+nextY);
            }
        }
        
        return;
    }
    

    }

    please see above, p1 & p2, if I check condition in p1 then it works, but if I check bound inside for loop as p2, it gets time out. Can someone explain it to me?


Log in to reply
 

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