I am having trouble understanding why placing visited.append((i,j)) in the else case gives me the right output, while keeping it as shown below gives the incorrect output.
I tried to debug with a simpler example
[[0,1],
[1,1]]
But I am not able to figure out why keeping it outside the else gives wrong result.
Code:
from typing import List
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
ni, nj = len(grid), len(grid[0])
visited = set()
def dfs(i, j):
nonlocal visited
if (i,j) in visited:
return 0
visited.add((i,j)) # Placing this inside else gives me right result
if i < 0 or j < 0 or i >= ni or j >= nj or grid[i][j] == 0:
return 1
else:
return dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
# U D L R
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 1:
return dfs(i, j)
print(Solution().islandPerimeter([[0,1],
[1,1]]))
>Solution :
If I had to guess, it probably has to do with the fact that you’re returning 1 instead of 0 depending on whether empty/out-of-bounds positions have been visited.
Taking this example:
01
11
You’re returning 1 in the following positions:
*
*1*
*11*
**
How many positions is that? Well, that depends on how you count them. If you count each one exactly once (visited is outside the else), there will be 7 positions.
If you count each one each time it’s adjacent to a 1 (visited is inside the else), there will be 8:
A
G1B
F11C
ED
A through F will be counted once each (for a total of 6), but G will be counted twice (once when visiting from its right, once when visiting from its bottom).
This is why it’s so important to be clear about what you’re counting. I imagine you’re being asked to determine the perimeter of this shape, which will be 8, not 7:
_
_| |
|_ _|