Problem implementing DFS to find islands in a matrix

Question

I'm trying to solve a leetcode problem called Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

class Solution(object):
    def numIslands(self, grid):
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0

        visited = [[False]*len(grid[0])]*len(grid)
        count = 0

        grid = [[int(k) for k in item] for item in grid]

        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                if visited[i][j] == False and grid[i][j] == 1:
                    print('new island---->', i, j)
                    count = count+1
                    self.dfs(grid, visited, i, j)

    def dfs(self, grid, visited, i, j):
        if i >= len(grid) or j >= len(grid[0]):
            return 
        elif grid[i][j] == 0:
            return 
        else:
            visited[i][j] = True
            self.dfs(grid, visited, i+1, j)
            self.dfs(grid, visited, i, j+1)

For some reason my visited matrix has entire column set to true after each dfs call. I'm not sure why and what's going wrong here

Possible duplicate of [List of lists changes reflected across sublists unexpectedly](https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly) — TrebledJ, Jan 09 '19 at 02:20

score 2 · Accepted Answer · answered Jan 09 '19 at 02:19

Note that multiplying a list creates multiple references to, not multiple copies of, the list in question. So [x] * 2 yields [x, x], not [copy.copy(x), copy.copy(x)], which is an important distinction if x is mutable. So when initializing visited, you'll want to use list comprehensions instead of list multiplication: [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]. This will create a new list for each element.

Because False is immutable, you can get away with using multiplication for the inner lists ([[False] * len(grid[0]) for _ in range(len(grid))]), but it's probably better to get in the habit of the former.

Problem implementing DFS to find islands in a matrix

1 Answers1