DFS & BFS Flood Fill Algorithm with C++


  • 6

    Standard Flood Fill algorithm implementation.

    DFS:

    class Solution {
    public:
        int m, n; 
        vector<vector<bool>> flag;
        int go[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
        void dfs(vector<vector<char>>& board, int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == '.' || flag[i][j]) return;
            flag[i][j] = true;
            for (int d = 0; d < 4; ++d) dfs(board, i+go[d][0], j+go[d][1]);
        }
    
        int countBattleships(vector<vector<char>>& board) {
            if (board.empty()) return 0;
            m = board.size(), n = board[0].size();
            flag.resize(m, vector<bool>(n, false));
            int result = 0;
            for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j)
                    if (board[i][j] == 'X' && !flag[i][j]) {
                        ++result;
                        dfs(board, i, j);
                    }
            return result;
        }
    };
    

    BFS:

    class Solution {
    public:
        int go[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int countBattleships(vector<vector<char>>& board) {
            if (board.empty()) return 0;
            int m = board.size(), n = board[0].size();
            vector<vector<bool>> flag(m, vector<bool>(n, false));
            int result = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (board[i][j] == 'X' && !flag[i][j]) {
                        ++result;
    
                        queue<pair<int, int>> q;
                        q.push({i, j});
                        while (!q.empty()) {
                            auto t = q.front(); q.pop();
                            flag[t.first][t.second] = true;
                            for (int d = 0; d < 4; ++d) {
                                int ni = t.first+go[d][0], nj = t.second+go[d][1];
                                if (ni < 0 || ni >= m || nj < 0 || nj >= n || board[ni][nj] == '.' || flag[ni][nj]) continue;
                                q.push({ni, nj});
                            }
                        }
                    }
                }
            }
            return result;
        }
    };
    

  • 0
    A
    This post is deleted!

  • 0
    J

    why is the second bfs? I think the idea of the first and the second is the same.


  • 0

    @jellywang0611
    DFS always search recursively, and BFS maintains a queue to extend level by level. They seem similar in this problem because of the flood fill algorithm.


  • 0
    V

    Would the DFS solution work for this test case ?

    . X . .
    X X X X
    . X . .

    I think it will output 1 for the above case, whereas leetcode's solution is 2.


  • 0
    A

    This is not a valid input right?

    1. "Battleships can only be placed horizontally or vertically."
    2. "At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships."

  • 0
    V

    @altair94

    . . . X
    XXXX
    . . . X

    This is invalid, and outputs 1. The previous case is valid, not a clear test case though, whose output is 2.


  • 0
    G

    @velripiku I don't think this is a valid board. I think leetcode gives a result instead of reminding us it is not valid just because the problem says assume a valid board.


  • 1

    Thanks for your sharing.

    I wanna add a code using DFS with stack. A Non-Recursion Algorithm.

    Hope you like

    const int go[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    
    class Solution
    {
    	public:
    
    
    	int countBattleships(vector<vector<char>>& board)
    	{
    		if(board.empty())
    		{
    			return 0;
    		}
    
    		int m = board.size();
    		int n = board[0].size();
    		vector<vector<bool>> flag(m, vector<bool>(n, false));
    		int res = 0;
    		for(int i = 0; i < m; ++i)
    		{
    			for(int j = 0; j < n; ++j)
    			{
    				if(board[i][j] == 'X'&&!flag[i][j])
    				{
    					flag[i][j] = true;
    					++res;
    					stack<pair<int, int>> st;
    					st.push({ i, j });
    
    					while(!st.empty())
    					{
    						auto t = st.top();
    
    						int d = 0;
    						for(; d < 4; ++d)
    						{
    							int ni = t.first + go[d][0];
    							int nj = t.second + go[d][1];
    							if(ni < 0 || ni >= m || nj < 0 || nj >= n ||
    							   board[ni][nj] == '.' || flag[ni][nj])
    							{
    								continue;
    							}
    							flag[ni][nj] = true;
    							st.push({ ni, nj });
    							break;
    						}
    						if(d == 4)
    						{
    							st.pop();
    						}
    
    					}
    
    				}
    			}
    		}
    		return res;
    	}
    };
    

    And I dont think it is good to declare go in the class Solution. I'm puzzled for that.
    int go[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};


  • 0
    C

    What is the time complexity of your solution?O(mn)?


Log in to reply
 

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