# Simple c++ dfs solution

• ``````class Solution {
public:
int numIslands(vector<vector<char>> &grid) {
int m = grid.size();
if (m==0) return 0;
int n = grid[0].size();
int count = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j]=='1') {
helper(grid,i,j,m,n);
count++;
}
}
}
return count;
}

void helper(vector<vector<char> >& a, int i, int j, int m, int n) {
a[i][j] = 0;
if (i > 0 && a[i-1][j]=='1') helper(a,i-1,j,m,n);
if (j > 0 && a[i][j-1]=='1') helper(a,i,j-1,m,n);
if (i < m-1 && a[i+1][j]=='1') helper(a,i+1,j,m,n);
if (j < n-1 && a[i][j+1]=='1') helper(a,i,j+1,m,n);
}
};``````

• Here is python version with similar thought:

``````def destroy_island(self, grid, visited, i, j, h, w):
# burn current spot
# burn to four directions
if i-1 >= 0 and grid[i - 1][j] == "1" and (i - 1, j) not in visited: self.destroy_island(grid, visited, i - 1, j, h, w)
if j-1 >= 0 and grid[i][j - 1] == "1" and (i, j - 1) not in visited: self.destroy_island(grid, visited, i, j - 1, h, w)
if i+1 < h and grid[i + 1][j] == "1" and (i + 1, j) not in visited: self.destroy_island(grid, visited, i + 1, j, h, w)
if j+1 < w and grid[i][j + 1] == "1" and (i, j + 1) not in visited: self.destroy_island(grid, visited, i, j + 1, h, w)

def numIslands(self, grid):
if not grid: return 0
visited = set()
counter = 0
n = len(grid)
m = len(grid[0])
for i in xrange(n):
for j in xrange(m):
if grid[i][j] == "1" and (i, j) not in visited:
counter += 1
self.destroy_island(grid, visited, i, j, n, m)

return counter
``````

• you dont have to use visited. just mark the position with "0" so that you wont see it again in your search

• The input for python are array of strings, so you need additional memory either ways

http://stackoverflow.com/questions/8680080/why-are-python-strings-immutable-best-practices-for-using-them

• ok, good to know. :)

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