Why DFS not working?


  • 0
    L

    I compared this problem with #695 (Max Area of Island). I was trying to use similar DFS solution to solve it. but it doesn't work properly. Anyone can point why?

        def maxKilledEnemies(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            l_row, l_col = len(grid), len(grid[0])
            visited = [[False] * l_col for _ in range(l_row)]
    
            def dfs(i, j):
                if 0 <= i < l_row and 0 <= j < l_col and not visited[i][j]:
                    visited[i][j] = True
                    if grid[i][j] == 'W':
                        return 0
                    elif grid[i][j] == '0':
                        top_val = dfs(i - 1, j)
                        down_val = dfs(i + 1, j)
                        left_val = dfs(i, j - 1)
                        right_val = dfs(i, j + 1)
                        return left_val + right_val + top_val + down_val
                    elif grid[i][j] == 'E':
                        top_val = dfs(i - 1, j)
                        down_val = dfs(i + 1, j)
                        left_val = dfs(i, j - 1)
                        right_val = dfs(i, j + 1)
                        return left_val + right_val + top_val + down_val + 1
                return 0
    
            ret = [0]
            for i in range(l_row):
                for j in range(l_col):
                    if not visited[i][j] and grid[i][j] == '0':
                        val = dfs(i, j)
                        ret[0] = max(val, ret[0])
            return ret[0]
    

Log in to reply
 

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