Skip to content

Instantly share code, notes, and snippets.

@davidrft
Created December 8, 2019 19:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save davidrft/c6897b5004d6f737c9263a1364983e35 to your computer and use it in GitHub Desktop.
Save davidrft/c6897b5004d6f737c9263a1364983e35 to your computer and use it in GitHub Desktop.
class Solution:
def buildGrid(self, stones):
gridSize = max(map(max, stones)) + 1
grid = [[0 for i in range(gridSize)] for i in range(gridSize)]
for x, y in stones:
grid[x][y] = 1
return grid, gridSize
def dfs(self, grid, i, j):
if grid[i][j] == 0: return
grid[i][j] = 0
for l in range(len(grid)):
self.dfs(grid, l, j,)
for k in range(len(grid)):
self.dfs(grid, i, k)
return
def removeStones(self, stones: List[List[int]]) -> int:
if not stones: return 0
islands = 0
grid, n = self.buildGrid(stones)
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
islands += 1
self.dfs(grid, i, j)
return len(stones) - islands
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment