Why this BFS code has TLE?


  • 0

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

  • 0
    U

    @xiaoyu.bai I know this is late but I just resolved the same problem from BFS. I got TLE because I didn't mark squares that are already in the queue as visited (using another symbol). Thus, some squares got re-added to the queue and wasted run-time and memory. DFS does not have the same problem since the algorithm mostly travels in one direction until it reaches the border.


Log in to reply
 

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