C++ 01 BFS | O(mn)
ApproachUse 0-1 BFS to traverse paths with minimal damage first. We can use a distance array to track the minimum damage taken from(0, 0)to(r, c).Complexity
Tim
# Approach
Use 0-1 BFS to traverse paths with minimal damage first. We can use a distance array to track the minimum damage taken from `(0, 0)` to `(r, c)`.

# Complexity
- Time complexity: $$O(mn)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(mn)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
      // Grid related quantities - size, boundaries, directions
      const int m = size(grid), n = size(grid[0]);
      const array<int, 5> dir {1, 0, -1, 0, 1};
      auto isValid = [m, n](int r, int c) {
        return 0 <= r && r < m && 0 <= c && c < n;
      };

      // Distance array (Dijsktra) -> min health lost from (0, 0) to (r, c)
      constexpr int SIZE = 50, INF = SIZE * SIZE;
      array<array<int, SIZE>, SIZE> d;
      for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
          d[i][j] = INF;

      d[0][0] = grid[0][0];

      // 0-1 BFS
      deque<pair<int, int>> q;
      q.push_back({0, 0});
      
      while (!q.empty()) {
        // Current cell to evaluate (r, c) (best possible paths are evaluated first)
        auto [r, c] = q.front(); q.pop_front();
        
        // The damage taken can only increase from here
        if (d[r][c] >= health) 
          return false;

        // Check if we have reached the destination
        if (r == m - 1 && c == n - 1)
          return true;

        for (int i = 0; i < 4; i++) {
          // Adjacent cell (nr, nc)
          int nr = r + dir[i], nc = c + dir[i + 1];

          // Can we reach (nr, nc) from (r, c) with more health than any previous path?
          if (isValid(nr,nc) && d[r][c] + grid[nr][nc] < d[nr][nc]) {

            // Update distance array
            d[nr][nc] = d[r][c] + grid[nr][nc];

            // Evaluate the 0 paths before the 1 paths
            if (grid[nr][nc] == 1)
              q.push_back({nr, nc});
            else
              q.push_front({nr, nc});
          }
        }
      }

      return false;
    }
};
```
['Breadth-First Search', 'C++']