# DFS & BFS Flood Fill Algorithm with C++

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

• This post is deleted!

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

• @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.

• 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.

• 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."

• @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.

• @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.

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

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

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