Time Limit Exceeded,why?


  • 0
    E

    I don't understand why my code exceeds the time limit. Queue is used, everything just like the other common solutions.

    public class Solution {

    public void solve(char[][] board) {
    	int row = board.length;
    	if (row <= 0)
    		return;
    	int column = board[0].length;
    	for (int i = 0; i < row; i++) {
    		if (board[i][0] == 'O') {
    			bfs(board, i, 0);
    		}
    		if (board[i][column - 1] == 'O') {
    			bfs(board, i, column - 1);
    		}
    	}
    	for (int i = 0; i < column; i++) {
    		if (board[0][i] == 'O') {
    			bfs(board, 0, i);
    		}
    		if (board[row - 1][i] == 'O') {
    			bfs(board, row - 1, i);
    		}
    	}
    	for (int i = 0; i < row; i++)
    		for (int j = 0; j < column; j++) {
    			if (board[i][j] == 'O')
    				board[i][j] = 'X';
    			if (board[i][j] == 'E')
    				board[i][j] = 'O';
    		}
    }
    
    public void bfs(char[][] board, int row, int column) {
    	Queue<Point> queue = new LinkedList<Point>();
    	queue.add(new Point(row, column));
    	while (!queue.isEmpty()) {
    		Point tmp = queue.poll();
    		int r = tmp.row;
    		int c = tmp.column;
    		board[r][c] = 'E';
    		if (r - 1 >= 0 && board[r - 1][c] == 'O') {
    			queue.add(new Point(r - 1, c));
    		}
    		if (r + 1 < board.length && board[r + 1][c] == 'O') {
    			queue.add(new Point(r + 1, c));
    		}
    		if (c - 1 >= 0 && board[r][c - 1] == 'O') {
    			queue.add(new Point(r, c - 1));
    		}
    		if (c + 1 < board[0].length && board[r][c + 1] == 'O') {
    			queue.add(new Point(r, c + 1));
    		}
    	}
    }
    

    }

    class Point {
    int row;
    int column;

    Point(int r, int c) {
    	row = r;
    	column = c;
    }
    

    }


  • 0
    J

    Nice thought! But the BFS is not correct! you need to have a Set<Point> to record the visited(queued) point during your BFS, so you will never re-push the visited(queued) point into the queue. Since you don't have
    the visit-keeper set, your bfs will not terminate, it will bounce between 2 point forever. And that is the reason why you got a TLE.


  • 0
    E

    thanks, I only consider that every 'O' only have one single chance being converted to 'E', now I understand.


  • 0
    A

    I don't understand. The queued point is being set to 'E', correct? And then you are checking for only 'O' points in the board. So how could you possibly re-push the point to the queue? Could you please elaborate? Thanks!
    Nvm, figured it out.


Log in to reply
 

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