[Python] BFS>Dijkstra>Bellman Ford(DP)
Code

# Code
```python3 []
# solution 1: dijkstra
# time: O((m*n) * log(m*n))
# space: O(m*n)


class Solution1:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        rows, cols = len(grid), len(grid[0])
        health_track = [[math.inf] * cols for _ in range(rows)]
        health_track[0][0] = 0 if grid[0][0] == 0 else 1
        pq = [(health_track[0][0], 0, 0)]

        while pq:
            curr_health, curr_x, curr_y = heapq.heappop(pq)
            if curr_health > health_track[curr_x][curr_y]:
                continue

            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr = dr + curr_x
                nc = dc + curr_y
                if 0 <= nr < rows and 0 <= nc < cols:
                    updated_health = curr_health + grid[nr][nc]
                    if updated_health < health_track[nr][nc] and updated_health < health:
                        heapq.heappush(pq, (updated_health, nr, nc))
                        health_track[nr][nc] = updated_health

        return health_track[rows - 1][cols - 1] < health


sol1 = Solution1()
print("solution 1:", sol1.findSafeWalk(
    grid=[[1, 1, 1], [1, 0, 1], [1, 1, 1]], health=5
))


# solution 2: bfs
# time: O((m*n)
# space: O(m*n)


class Solution2:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        rows, cols = len(grid), len(grid[0])
        health_track = [[math.inf] * cols for _ in range(rows)]
        health_track[0][0] = 0 if grid[0][0] == 0 else 1
        queue = deque([(health_track[0][0], 0, 0)])

        while queue:
            curr_health, curr_x, curr_y = queue.popleft()
            if curr_health > health_track[curr_x][curr_y]:
                continue

            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr = dr + curr_x
                nc = dc + curr_y
                if 0 <= nr < rows and 0 <= nc < cols:
                    updated_health = curr_health + grid[nr][nc]
                    if updated_health < health_track[nr][nc] and updated_health < health:
                        queue.append((updated_health, nr, nc))
                        health_track[nr][nc] = updated_health

        return health_track[rows - 1][cols - 1] < health


# solution 3: bellman ford
# time: O((m*n)^2)
# space: O(m*n)


class Solution3:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        rows, cols = len(grid), len(grid[0])
        dp = [[math.inf] * cols for _ in range(rows)]
        dp[0][0] = grid[0][0]

        for _ in range(rows * cols - 1):
            updated = False
            for r in range(rows):
                for c in range(cols):
                    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < rows and 0 <= nc < cols:
                            updated_health = dp[r][c] + grid[nr][nc]
                            if dp[nr][nc] > updated_health:
                                dp[nr][nc] = updated_health
                                updated = True

            if not updated:
                break

        return dp[rows - 1][cols - 1] < health

```
['Dynamic Programming', 'Breadth-First Search', 'Shortest Path', 'Python3']