C++ | beats 100% | Djikstra Algo
ApproachLet us rephrase question we find path from 0,0 to m-1,n-1
such that no. of 1s are minimised in the path using djikstrathen we return health > minimumNo.

# Approach
<!-- Describe your approach to solving the problem. -->
Let us rephrase question we find path from 0,0 to m-1,n-1 
such that no. of 1s are minimised in the path using djikstra

then we return health > minimumNo. of ones needed

this will be approach to solve it

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

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

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

        // cost matrix is no. of 1s in path
        vector<vi> dist(m, vi(n, INT_MAX));

        dist[0][0] = grid[0][0];
        priority_queue<vi, vector<vi>, greater<vi>> pq;
        pq.push({dist[0][0], 0, 0});

        int d, x, y, nx, ny;
        while (!pq.empty()) {
            d = pq.top()[0];
            x = pq.top()[1];
            y = pq.top()[2];
            pq.pop();

            if (x == m - 1 && y == n - 1)
                return health > d;

            vi dir = {-1, 0, 1, 0, -1};

            for (int i = 0; i < 4; i++) {
                nx = x + dir[i];
                ny = y + dir[i + 1];

                if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                    int newCost = grid[nx][ny] + d;
                    if (newCost < dist[nx][ny]) {
                        dist[nx][ny] = newCost;
                        pq.push({newCost, nx, ny});
                    }
                }
            }
        }

        return false;
    }
};
```
['C++']