Simple BFS
IntuitionThe goal is to determine whether we can safely walk from the top-left corner (0,0) to the bottom-right corner (m-1, n-1) while maintaining a positive h
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The goal is to determine whether we can safely walk from the top-left corner (0,0) to the bottom-right corner (m-1, n-1) while maintaining a positive health. So we dont need to find the shortest path, we can just compute the safest path.

# Approach
<!-- Describe your approach to solving the problem. -->
We run a BFS:
1. Initialize a visited matrix with health 0 for each element
2.  Update visited[0][0] and push node (0,0) into the queue
3. For each cell adj cell, if hp-grid[i][j] > visited[i][j]:
    - If we reach the (n-1,m-1) -> return True
    - True: update visited[i][j] with hp-grid[i][j] and push (i,j) into the queue
    - False: move onto next iteration
4. Return False


# 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) {
        if(health==0){
            return false;
        }
        vector<vector<int>>visited(grid.size(),vector<int>(grid[0].size(),0));
        queue<pair<int,pair<int,int>>>q;
        health=grid[0][0]?health-1:health;
        q.push({health,{0,0}});
        visited[0][0]=health;
        vector<pair<int,int>>dir={{-1,0},{0,-1},{0,1},{1,0}};
        while(!q.empty()){
            int hp=q.front().first;
            auto [x,y]=q.front().second;
            q.pop();
            for(auto [dx,dy]:dir){
                int nx=x+dx;
                int ny=y+dy;
                if(nx<0 || ny<0 || nx==grid.size() || ny==grid[0].size()){
                    continue;
                }
                if(hp-grid[nx][ny]>0){
                    int h=hp-grid[nx][ny];
                    if(h>visited[nx][ny]){
                        visited[nx][ny]=h;
                        if(nx==grid.size()-1 && ny==grid[0].size()-1){
                            return true;
                        }
                        q.push({h,{nx,ny}});
                    }
                }
            }
        }
        return false;
    }
};
```
['Breadth-First Search', 'Matrix', 'C++']