Why this BFS method get "Time Limit Exceeded" for large case


  • 0
    H

    This is just a standard BFS method, looks very like others BFS who got accepted. It passes the first 28 cases, but got "Time Limit Exceeded" for case 29 which is a large case. Would anyone has a clue?

    Thanks!

    public class Solution {
        int row;
        int col;
        int[] dx = {0,0,1,-1,1,1,-1,-1};
        int[] dy = {1,-1,0,0,-1,1,1,-1};
        public char[][] updateBoard(char[][] board, int[] click) {
            if (click.length==0)    return board;
            LinkedList<Integer> queue = new LinkedList<Integer>();
            LinkedList<Integer> q2 = new LinkedList<Integer>();
            
            int x = click[0]; int y = click[1];
            if (board[x][y] == 'M'){
                board[x][y] = 'X';
                return board;
            }
    
            row = board.length;
            col = board[0].length;
            queue.offer(x*col + y);
    
            while (!queue.isEmpty()){
                int cur = queue.poll();
                x = cur/col;
                y = cur%col;
                if (board[x][y]=='M')   continue;
    
                int neighborMineNumber = 0;
    
                for (int i=0; i<8; i++){
                    int newx = x+dx[i];
                    int newy = y+dy[i];
                    if (newx<0 || newy<0 || newx>=row || newy>=col || (board[newx][newy]!='M' && board[newx][newy]!='E')) continue;
                    if (board[newx][newy]=='M') neighborMineNumber++;
                    else if (board[newx][newy]=='E'){
                        q2.offer(newx*col + newy);
                    }
                }
    
                if (neighborMineNumber==0) {
                    board[x][y] = 'B';
                    while (q2.size()>0)   queue.offer(q2.poll());
                }
                else{
                    board[x][y] = (char)(neighborMineNumber+'0');
                }
                q2.clear();
            }
    
            return board;
        }
    }
    

Log in to reply
 

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