3286. Find a Safe Walk Through a Grid

You are given an m x n binary matrix grid and an integer health.

You start on the upper-left corner (0, 0) and would like to get to the lower-right corner (m - 1, n - 1).

You can move up, down, left, or right from one cell to another adjacent cell as long as your health remains positive.

Cells (i, j) with grid[i][j] = 1 are considered unsafe and reduce your health by 1.

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

class Solution {
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> cost(n,vector<int>(m));
        queue<pair<int,int>> ZERO, ONE;
        auto push = [&](int y, int x, int c) {
            if(cost[y][x] < c) {
                if(grid[y][x]) ONE.push({y,x});
                else ZERO.push({y,x});
                cost[y][x] = c;
            }
        };
        push(0,0,health - grid[0][0]);
        int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
        while(ZERO.size() or ONE.size()) {
            while (ZERO.size()) {
                auto [y,x] = ZERO.front(); ZERO.pop();
                for(int i = 0; i < 4; i++) {
                    int ny = y + dy[i], nx = x + dx[i];
                    if(0 <= ny and ny < n and 0 <= nx and nx < m) {
                        push(ny,nx,cost[y][x] - grid[ny][nx]);
                    }
                }
            }
            while(ONE.size() and !ZERO.size()) {
                auto [y,x] = ONE.front(); ONE.pop();
                for(int i = 0; i < 4; i++) {
                    int ny = y + dy[i], nx = x + dx[i];
                    if(0 <= ny and ny < n and 0 <= nx and nx < m) {
                        push(ny,nx,cost[y][x] - grid[ny][nx]);
                    }
                }
            }
        }
        return cost[n-1][m-1] > 0;
    }
};