Why this BFS code has TLE?


  • 0
    X

    The code below is very similar to people's accepted BFS code. But it yields TLE after 28 cases when reaching a large case. Could somebody point out where the problem is please? Thanks in advance!

    public class Solution {
        public char[][] updateBoard(char[][] board, int[] click) {
            int m = board.length;
            if(m == 0)  return board;
            int n = board[0].length;
            if(n == 0)  return board;
            Queue<int[]> queue = new LinkedList<>();
            queue.add(click);
            int[][] dirs = new int[][]{{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};
            while(!queue.isEmpty()) {
                int[] curr = queue.poll();
                if(board[curr[0]][curr[1]] == 'M') {
                    board[curr[0]][curr[1]] = 'X';
                    continue;
                }
                int count = 0;
                for(int[] dir : dirs) {
                    int row = curr[0] + dir[0];
                    int col = curr[1] + dir[1];
                    if(row >= 0 && row < m && col >= 0 && col < n && (board[row][col] == 'M' || board[row][col] == 'X'))
                        count++;
                }
                if(count > 0) {
                    board[curr[0]][curr[1]] = (char) ('0'+count);
                    continue;
                }
                board[curr[0]][curr[1]] = 'B';
                for(int[] dir : dirs) {
                    int row = curr[0] + dir[0];
                    int col = curr[1] + dir[1];
                    if(row >= 0 && row < m && col >= 0 && col < n && board[row][col] == 'E')
                        queue.add(new int[]{row, col});
                }
            }
            return board;
        }
    }
    

Log in to reply
 

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