# 4ms C DFS solution reusing grid to memoize visited squares

• ``````bool visit(char **grid, int numRows, int numColumns, int x, int y)
{
if ( x <0 || y < 0 || x >= numColumns || y >= numRows || grid[y][x] != '1')
return false;

grid[y][x] = 'v'; //visited

visit(grid, numRows, numColumns, x + 1, y);
visit(grid, numRows, numColumns, x - 1, y);
visit(grid, numRows, numColumns, x, y + 1);
visit(grid, numRows, numColumns, x, y -1);

return true;
}

int numIslands(char **grid, int numRows, int numColumns)
{
int total = 0;
for (int y=0; y < numRows; y++)
for (int x=0; x < numColumns; x++)
total += visit(grid, numRows, numColumns, x, y) ? 1 : 0;

}``````

• ``````public class Solution {
public int numIslands(char[][] grid) {
int count=0;
for(int x=0;x<grid.length;x++){
for(int y=0;y<grid[0].length;y++){
if(visit(grid,x,y)) count++;
}
}
return count;
}
private boolean visit(char[][] grid, int x, int y){
if(x<0||y<0||x>=grid.length||y>=grid[0].length|| grid[x][y]!='1') return false;
grid[x][y]='v';
visit(grid, x-1,y);
visit(grid, x,y-1);
visit(grid, x+1,y);
visit(grid, x,y+1);
return true;
}
}``````

• Nice solution, here is a Python version:

``````# DFS
def numIslands(self, grid):
if not grid:
return 0
num = 0
row, col = len(grid), len(grid[0])
for i in xrange(row):
for j in xrange(col):
if self.visit(grid, i, j):
num += 1
return num

def visit(self, grid, i, j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != "1":
return False
grid[i][j] = "0"
self.visit(grid, i-1, j)
self.visit(grid, i+1, j)
self.visit(grid, i, j-1)
self.visit(grid, i, j+1)
return True``````

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