Leet Code Daily 2024-05-15 - Find the Safest Path in a Grid

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

class Solution {
public:
    vector<vector<int>> bfs(vector<vector<int>>& grid, const int n) {
        vector<vector<int>> f(n, vector<int>(n, -1));
        queue<pair<int, int>> q;
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                if (grid[x][y] == 1) {
                    f[x][y] = 0;
                    q.push(make_pair(x, y));
                }
            }
        }
        for (; !q.empty(); q.pop()) {
            auto [x, y] = q.front();
            for (const auto& d : kDir) {
                const int nx = x + d.first, ny = y + d.second;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && f[nx][ny] == -1) {
                    f[nx][ny] = f[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
        return f;
    }

    int spfa(vector<vector<int>> f, const int n) {
        vector<vector<int>> g(n, vector<int>(n, INT_MIN));
        queue<pair<int, int>> q;
        g[0][0] = f[0][0];
        q.push(make_pair(0, 0));
        for (; !q.empty(); q.pop()) {
            auto [x, y] = q.front();
            for (const auto& d : kDir) {
                const int nx = x + d.first, ny = y + d.second;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    const int ng = min(g[x][y], f[nx][ny]);
                    if (g[nx][ny] < ng) {
                        g[nx][ny] = ng;
                        q.push(make_pair(nx, ny));
                    }
                }
            }
        }
        return g[n - 1][n - 1];
    }

    int maximumSafenessFactor(vector<vector<int>>& grid) {
        const int n = grid.size();
        return spfa(bfs(grid, n), n);
    }
};