CODEWITHSUNDEEP
pythonbreadth-first-search
csguy
csguy

Reputation: 1484

BFS same way different result (python)

Problem: https://leetcode.com/problems/number-of-islands/

Trying to figure out why calling the bfs function results in "correct" behavior according to the testcases, while just writing the plain code with no function call does not. It's literally the same code.

class Solution:

    def bfs(self, grid, queue):
       
        while len(queue) != 0:
            
            i, j = queue.pop(0)

            if i - 1 >= 0 and grid[i - 1][j] == "1":
                grid[i - 1][j] = "0"
                queue.append((i - 1, j))

            if i + 1 < len(grid) and grid[i + 1][j] == "1":
                grid[i + 1][j] = "0"
                queue.append((i + 1, j))

            if j - 1 >= 0 and grid[i][j - 1] == "1":
                grid[i][j - 1] = "0"
                queue.append((i, j - 1))

            if j + 1 < len(grid[i]) and grid[i][j + 1] == "1":
                grid[i][j + 1] = "0"
                queue.append((i, j + 1))

            
    def numIslands(self, grid: List[List[str]]) -> int:

        sol = 0

        for i in range(0, len(grid), 1):
            for j in range(0, len(grid[i]), 1):

                if grid[i][j] == "1":
                    sol += 1
            
                    queue = [(i, j)]

                    grid[i][j] = "0"
                    
# calling the function does different behavior
#                     self.bfs(grid, queue)
    
# as opposed to not calling the bfs function:           
#                     while len(queue) != 0:
#                         print(queue)
#                         i, j = queue.pop(0)

#                         if i - 1 >= 0 and grid[i - 1][j] == "1":
#                             grid[i - 1][j] = "0"
#                             queue.append((i - 1, j))

#                         if i + 1 < len(grid) and grid[i + 1][j] == "1":
#                             grid[i + 1][j] = "0"
#                             queue.append((i + 1, j))

#                         if j - 1 >= 0 and grid[i][j - 1] == "1":
#                             grid[i][j - 1] = "0"
#                             queue.append((i, j - 1))

#                         if j + 1 < len(grid[i]) and grid[i][j + 1] == "1":
#                             grid[i][j + 1] = "0"
#                             queue.append((i, j + 1))

        return sol

Testcase:

[["1","0","0","1","1","1","0","1","1","0","0","0","0","0","0","0","0","0","0","0"],["1","0","0","1","1","0","0","1","0","0","0","1","0","1","0","1","0","0","1","0"],["0","0","0","1","1","1","1","0","1","0","1","1","0","0","0","0","1","0","1","0"],["0","0","0","1","1","0","0","1","0","0","0","1","1","1","0","0","1","0","0","1"],["0","0","0","0","0","0","0","1","1","1","0","0","0","0","0","0","0","0","0","0"],["1","0","0","0","0","1","0","1","0","1","1","0","0","0","0","0","0","1","0","1"],["0","0","0","1","0","0","0","1","0","1","0","1","0","1","0","1","0","1","0","1"],["0","0","0","1","0","1","0","0","1","1","0","1","0","1","1","0","1","1","1","0"],["0","0","0","0","1","0","0","1","1","0","0","0","0","1","0","0","0","1","0","1"],["0","0","1","0","0","1","0","0","0","0","0","1","0","0","1","0","0","0","1","0"],["1","0","0","1","0","0","0","0","0","0","0","1","0","0","1","0","1","0","1","0"],["0","1","0","0","0","1","0","1","0","1","1","0","1","1","1","0","1","1","0","0"],["1","1","0","1","0","0","0","0","1","0","0","0","0","0","0","1","0","0","0","1"],["0","1","0","0","1","1","1","0","0","0","1","1","1","1","1","0","1","0","0","0"],["0","0","1","1","1","0","0","0","1","1","0","0","0","1","0","1","0","0","0","0"],["1","0","0","1","0","1","0","0","0","0","1","0","0","0","1","0","1","0","1","1"],["1","0","1","0","0","0","0","0","0","1","0","0","0","1","0","1","0","0","0","0"],["0","1","1","0","0","0","1","1","1","0","1","0","1","0","1","1","1","1","0","0"],["0","1","0","0","0","0","1","1","0","0","1","0","1","0","0","1","0","0","1","1"],["0","0","0","0","0","0","1","1","1","1","0","1","0","0","0","1","1","0","0","0"]]

calling function returns the expected solution: 58 while not calling returns: 47

Upvotes: 0

Views: 59

Answers (1)

Pychopath
Pychopath

Reputation: 1580

Big picture view of your solution:

        for i in range(0, len(grid), 1):
            for j in range(0, len(grid[i]), 1):
                run BFS

If you write the BFS code right there, it messes up the variable i from that outer loop (also j, but that doesn't matter). If you instead call the function, that function has its own local variable i and doesn't mess up the loop's.

Upvotes: 1

Related Questions