My BFS solution (C++ 28ms)


  • 66
    E

    The algorithm is quite simple: Use BFS starting from 'O's on the boundary and mark them as 'B', then iterate over the whole board and mark 'O' as 'X' and 'B' as 'O'.

    void bfsBoundary(vector<vector<char> >& board, int w, int l)
    {
        int width = board.size();
        int length = board[0].size();
        deque<pair<int, int> > q;
        q.push_back(make_pair(w, l));
        board[w][l] = 'B';
        while (!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop_front();
            pair<int, int> adjs[4] = {{cur.first-1, cur.second}, 
                {cur.first+1, cur.second}, 
                {cur.first, cur.second-1},
                {cur.first, cur.second+1}};
            for (int i = 0; i < 4; ++i)
            {
                int adjW = adjs[i].first;
                int adjL = adjs[i].second;
                if ((adjW >= 0) && (adjW < width) && (adjL >= 0)
                        && (adjL < length) 
                        && (board[adjW][adjL] == 'O')) {
                    q.push_back(make_pair(adjW, adjL));
                    board[adjW][adjL] = 'B';
                }
            }
        }
    }
    
    void solve(vector<vector<char> > &board) {
        int width = board.size();
        if (width == 0) //Add this to prevent run-time error!
            return;
        int length = board[0].size();
        if  (length == 0) // Add this to prevent run-time error!
            return;
    
        for (int i = 0; i < length; ++i)
        {
            if (board[0][i] == 'O')
                bfsBoundary(board, 0, i);
    
            if (board[width-1][i] == 'O')
                bfsBoundary(board, width-1, i);
        }
    
        for (int i = 0; i < width; ++i)
        {
            if (board[i][0] == 'O')
                bfsBoundary(board, i, 0);
            if (board[i][length-1] == 'O')
                bfsBoundary(board, i, length-1);
        }
    
        for (int i = 0; i < width; ++i)
        {
            for (int j = 0; j < length; ++j)
            {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == 'B')
                    board[i][j] = 'O';
            }
        }
    }
    

    Note that one of the test cases is when the board is empty. So if you don't check it in your code, you will encounter an run-time error.


  • -1
    G

    is BFS the best option for this problem? Here's my DFS code(48ms) just for reference. seems my code requires less spaces compared with the deque u . What do u think =,=

    class Solution {
    public:
        void solve(vector<vector<char>> &board) {
            int n = board.size();//row
            int line = 0;//column
            if (n>=1) line = board[0].size();
            if (n>2 && line >2) {
         
                for (int i=0;i<n;i++){
                    if (board[i][0]=='O') {
                        board[i][0] = 'p';
                        if (board[i][1] == 'O'&&i!=0&&i!=n-1) search(i,1,board,n,line);
                    }
                    if (board[i][line-1]=='O'){
                        board[i][line-1] ='p';
                        if (board[i][line-2] == 'O'&&i!=0&&i!=n-1) search(i,line-2,board,n,line);
                    }
                }
                
                for (int i=0;i<line;i++){
                    if (board[0][i]=='O'){
                        board[0][i] = 'p';
                        if (board[1][i] =='O'&&i!=0&&i!=line-1) search(1,i,board,n,line);
                    }
                    if (board[n-1][i]=='O'){
                        board[n-1][i] = 'p';
                        if (board[n-2][i] =='O'&&i!=0&&i!=line-1) search(n-2,i,board,n,line);
                }
                }
                  
                for (int i=0;i<n;i++)
                    for (int j=0;j<line;j++)
                        board[i][j] = (board[i][j] == 'p')?'O':'X';
                        
            }
        }
        
        void search(int i,int j,vector<vector<char>> &board,int n,int line){
            board[i][j]='p';
            if (i<n-2 && board[i+1][j]=='O') search(i+1,j,board,n,line);
            if (i>1 && board[i-1][j]=='O') search(i-1,j,board,n,line);
            if (j<line-2 && board[i][j+1]=='O') search(i,j+1,board,n,line);
            if (j>1 && board[i][j-1]=='O') search(i,j-1,board,n,line);
        }
    };

  • 0
    E

    Considering the space used by the calling stack, I think DFS uses almost the same space as BFS.


  • 0
    I

    Awesome solution! Like this one so much


  • 0

    Likes your idea that only check '0' on the boundary and their adjacent nodes if it is 0. Saved lots of checks. +1!


  • -1
    L

    My version of search: (Thanks jakwings' correction)

    class Solution {
    public:
        void solve(vector<vector<char>> &board) {
    		if (board.empty())
    			return;
    
    		// Init
    		int row = board.size();
    		int col = board.front().size();
    		vector< vector<int> > visited;
    		visited.resize(row);
    		for (auto & x : visited) {
    			x.resize(col);
    		}
    
    		for (int i = 0; i < row; ++i) {
    			visited[i][0] = (board[i][0] == 'O');
    			visited[i][col - 1] = (board[i][col - 1] == 'O');
    		}
    		for (int i = 0; i < col; ++i) {
    			visited[0][i] = (board[0][i] == 'O');
    			visited[row - 1][i] = (board[row - 1][i] == 'O');
    		}
    
    		// Flood
    		int stepx[4] = {-1, 0, 1, 0};
    		int stepy[4] = {0, 1, 0, -1};
    		bool find = true;
    		while (find) {
    			find = false;
    			for (int i = 0; i < row; ++i) {
    				for (int j = 0; j < col; ++j) if (board[i][j] == 'O' && !visited[i][j]) {
    					for (int k = 0; k < 4; ++k) {
    						int tx = i + stepx[k];
    						int ty = j + stepy[k];
    						if (0 <= tx && tx < row && 0 <= ty && ty < col) {
    							visited[i][j] |= visited[tx][ty];
    						}
    					}
    					if (visited[i][j])
    						find = true;
    				}
    			}
    		}
    
    		for (int i = 0; i < row; ++i)
    			for (int j = 0; j < col; ++j)
    				if (board[i][j] == 'O' && !visited[i][j])
    					board[i][j] = 'X';
        }
    };
    

  • 0
    E

    If I put the "board[adjW][adjL] = 'B';" outside the for loop and change it to "board[cur.first][cur.second] = 'B';", I will get a TLE...


  • 0
    J

    I think it is just brute force.


  • 0
    J

    I think it is DFS, not BFS, since it will just enter one of the adjacent grids at a time.


  • 0
    L

    You can see it as a brute force solution. And do you see BFS strategy from the code?
    A general BFS uses a queue to save start nodes of 'O', and then expand O's area in all directions but doesn't go deep into one direction.
    This code shares the same idea: each round, it adds 'O', which directly connects to boundary of 'O' area. The difference with general BFS is that it doesn't use a queue.
    The purpose of sharing this code is:
    1.provide another perspective of one algo. We can have the same logic with different implement.

    1. the efficiency of this code is as good as "eaglesky1990"'s on this OJ. This is an interesting thing, and I guess admin needs improve test cases.

  • 0
    J

    Please consider such cases:

    XXXXXXXXXXXXXXXXXXXX…X
    XOOOOOOOOOOOOOOOOOOO…O
    XXXXXXXXXXXXXXXXXXXX…X
    XOOOOOOOOOOOOOOOOOOO…O
    XOOOOOOOOOOOOOOOOOOO…O
    XOOOOOOOOOOOOOOOOOOO…O
    XOOOOOOOOOOOOOOOOOOO…O
    XOOOOOOOOOOOOOOOOOOO…O
    XXXXXXXXXXXXXXXXXXXX…X
    

  • 0
    L

    It's a very good example for efficiency issue. That's why i say test case needs to be improved. And the key point is that we can have multi ways for one idea, just like this code shares BFS strategy. Does it make sense?


  • 0
    J

    But your solution takes O(N^3) time instead of O(N^2) time, and it is not BFS since it doesn't search as more adjacent nodes as possible.


  • 0
    L

    You are talking about two things:

    1. time complicity. This is not your original concern -- your original one is the solution is not BFS. If you still have concern about time, please see my previous comment. Let's focus on BFS.
    2. it is not BFS since it doesn't search as more adjacent nodes as possible. Each round, it will find all 'O' at boundary of the selected 'O'. This is exactly BFS's idea. Or let's see it in this way, general BFS with queue visits one node in each round, while this code visit one table in each round. Do you find that they shares the same pattern?

  • 0
    J

    I know I'm not talking about the real elapsed time which depends on how complex the calculation is, but time complexity. Let's come back to BFS. ;-)

    You don't have an effective way to tell if an O is at the boundary. You just calculate for every O that is not “visited”. Just see the case I mentioned above and you will know.


  • 0
    L

    I agreed with your comments about time complexity from the very beginning, like i said, "admin needs improve test cases", and i also pointed out your case is a good one. So we can close here if all your points are about complexity.
    It's another way to implement BFS, because the key idea is BFS. Using queue is a obviously optimization. Do we agree with this one? If so, we can close here as well. :)


  • 0
    J

    No, it is definitely not BFS. Searching and breadth-first searching is not the same thing. Unless the targets are already with a good data structure for BFS, you must do some caching for it.

    It's sure that marking a node as “visited” can filter the targets. But BFS is a better filtering technique. It not only does marking, but also know what are the next targets (neighbors) exactly. If you think your solution is using BFS, you can try to solve another puzzle using two nested loops and O(1) space with simple calculations: First Missing Positive


  • 0
    J

    Let's try this board:

    vector<vector<char>> board;
    int rows = 1000, cols = 1000;
    for (int i = 0; i < rows; i++) {
        if (i == 0 || i == rows - 1) {
            board.push_back(vector<char>(cols, 'X'));
        } else {
            board.push_back(vector<char>(cols, 'O'));
            board[i][0] = 'X';
        }
    }
    

    @eaglesky1990 's solution use 0.15s, yours 40s.


  • 0
    L

    Again, please don't mix the two things into one. Time complexity doesn't matter with our topic. Also please think about the key point of BFS. It's traverse strategy but not a filtering technique. Please see wiki: http://en.wikipedia.org/wiki/Breadth-first_search and http://en.wikipedia.org/wiki/Graph_traversal

    FYI.
    In graph theory, breadth-first search (BFS) is a strategy for searching in a graph. BFS visits the parent nodes before visiting the child nodes.

    Seems your focus of BFS is on data structure/cache ... But my understanding is the strategy is the core.


  • 0
    E

    @jakwings: You mean the bfsBoundary routine should be DFS rather than BFS? I don't think so because that routine works as finding all the adjacent grids and then checks them one by one using a queue, which is a procedure of BFS not DFS. In addition, can DFS be implemented using a queue?


Log in to reply
 

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