DFS C++ 9ms

• If we encounter an unvisited grid, then increase the island number (count++), mark the grid as visited. Then start from the grid, mark all connected '1' grids as visited (use DFS).
Finally, return 'count'.

Similar to connected component problem.

``````class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
queue<pair<int,int>> myqueue;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == '1') {
count++;
myqueue.push(make_pair(i,j));
grid[i][j] = 'a';
}
while (!myqueue.empty()) {
pair<int,int> mypair = myqueue.front();
int m = mypair.first;
int n = mypair.second;
myqueue.pop();
if (m-1 >= 0) {
if (grid[m-1][n] == '1') { grid[m-1][n] = 'a'; myqueue.push(make_pair(m-1,n)); }
}
if (m+1 < grid.size()) {
if (grid[m+1][n] == '1') { grid[m+1][n] = 'a'; myqueue.push(make_pair(m+1,n)); }
}
if (n-1 >= 0) {
if (grid[m][n-1] == '1') { grid[m][n-1] = 'a'; myqueue.push(make_pair(m,n-1)); }
}
if (n+1 < grid[0].size()) {
if (grid[m][n+1] == '1') { grid[m][n+1] = 'a'; myqueue.push(make_pair(m,n+1)); }
}
}
}
}
return count;
}
};
``````

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