C++ | BFS
ApproachSimple BFSComplexity

Time complexity:
O(nmhealth)


Space complexity:
O(nmhealth)

Code
# Approach
Simple BFS 

# Complexity
- Time complexity:
O(n*m*health)

- Space complexity:
O(n*m*health)

# Code
```cpp []
class Solution {
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int rows = grid.size();
        int cols = grid[0].size();

        int bfs_level = 0;

        // At each vis[row][col] -> Count of Health left till visiting current row & col
        vector<vector<int>> vis(rows, vector<int>(cols, -1));

        queue<tuple<int, int, int>> q; // current health, curr_row, curr_col
        q.push({health - grid[0][0], 0, 0});

        // Edge case at starting point
        vis[0][0] = health - grid[0][0];

        int dir[4][2] = {
            {0, 1}, {0, -1}, {-1, 0}, {1, 0}}; // right, left, top, bottom

        while (q.size() > 0) {
            int size_of_queue = q.size();
            while (size_of_queue-- > 0) {
                auto [health_left, curr_row, curr_col] = q.front();
                q.pop();

                if ((curr_row == rows - 1 && curr_col == cols - 1)) {
                    return true;
                }

                for (int k = 0; k < 4; k++) {
                    int new_row = curr_row + dir[k][0];
                    int new_col = curr_col + dir[k][1];

                    if (new_row >= 0 && new_row < rows && new_col >= 0 &&
                        new_col < cols) {
                        int new_health_count =
                            health_left - grid[new_row][new_col];

                        // Found a better path, where we have more health at
                        // current cell
                        if (new_health_count > 0 && new_health_count > vis[new_row][new_col]) {
                            q.push({new_health_count, new_row, new_col});
                            vis[new_row][new_col] = new_health_count;
                        }
                    }
                }
            }
            bfs_level++;
        }
        return false;
    }
};
```
['C++']