BFS | Dijkstra
Code

# Code
```cpp []
/*

Problem: Find a Safe Walk Through a Grid

    Given:
        binary grid, health
        Start point: Upper left -- (0,0)
        End point:   lower-right corner (m - 1, n - 1)
        Directions: up, down, left, or right
        Condition on moving to next cell :  health remains positive

        Cell Behaviour: grid[i][j] = 1 are considered unsafe and reduce your health by 1.


    Requirements:
        Return true if you can reach the final cell with a health value of 1 or more, and false otherwise.

    Approaches:
        DFS : will give longest path and health may become negative
                not a good approach for this problem
        
        BFS: will give shortest path from start to end ensuring that
                minimum health is used
                TC: O(m * n)

        Djikstra: will work here
                TC: O(m * n * log(m*n))

        A-star: best optimal for large grids in real world applications

*/

class Solution {
public:

    int m, n;

    vector<pair<int, int>> directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};

    bool is_valid_cell(int r, int c)
    {
        return r>=0 && r<m && c>=0 && c<n;
    }

    bool findSafeWalk(vector<vector<int>>& grid, int health)
    {
        m = grid.size(), n = grid[0].size();

        // return solve_bfs(grid, health);

        return solve_dijkstra(grid, health);
    }

    bool solve_bfs(vector<vector<int>>& grid, int health)
    {
        // Track max health at each cell
        vector<vector<int>> visited(m, vector<int>(n, -1));

        // BFS queue of cell (row, col)
        queue<pair<int, int>> que;

        // add start point to queue
        que.push({0,0});

        int start_health = health - grid[0][0];

        // If we die at the start, no point continuing
        if (start_health < 1)
            return false;

        visited[0][0] = start_health;

        // BFS algorithm
        while(!que.empty())
        {
            auto [row, col] = que.front();

            que.pop();

            // reach end point
            if (row == m-1 && col == n-1 && visited[row][col] >= 1)
            {
                return true;
            }

            // explore neighbours
            for (auto [dr, dc] : directions)
            {
                int nr = row + dr;
                int nc = col + dc;

                if (is_valid_cell(nr, nc))
                {
                    int new_health = visited[row][col] - grid[nr][nc];

                    if (new_health >= 1 && new_health > visited[nr][nc])
                    {
                        visited[nr][nc] = new_health;
                        que.push({nr, nc});
                    }
                }
            }

        }
        return false;
    }

    bool solve_dijkstra(vector<vector<int>>& grid, int health)
    {
        priority_queue<tuple<int, int, int>> pq;  // (health, row, col) max heap
        pq.push({health - grid[0][0], 0, 0}); // Start with max health

        vector<vector<int>> visited(m, vector<int>(n, -1)); // Track best health
        visited[0][0] = health - grid[0][0];

        while (!pq.empty()) {
            auto [curr_health, row, col] = pq.top();
            pq.pop();

            if (row == m - 1 && col == n - 1 && curr_health >= 1)
                return true;

            for (auto [dr, dc] : directions) {
                int nr = row + dr, nc = col + dc;
                if (is_valid_cell(nr, nc)) {
                    int new_health = curr_health - grid[nr][nc];

                    if (new_health >= 1 && new_health > visited[nr][nc]) {
                        visited[nr][nc] = new_health;
                        pq.push({new_health, nr, nc});
                    }
                }
            }
        }
        return false;
    }
};
```
['C++']