2852. Sum of Remoteness of All Cells

You are given a 0-indexed matrix grid of order n * n. Each cell in this matrix has a value grid[i][j], which is either a positive integer or -1 representing a blocked cell.

You can move from a non-blocked cell to any non-blocked cell that shares an edge.

For any cell (i, j), we represent its remoteness as R[i][j] which is defined as the following:

• If the cell (i, j) is a non-blocked cell, R[i][j] is the sum of the values grid[x][y] such that there is no path from the non-blocked cell (x, y) to the cell (i, j).
• For blocked cells, R[i][j] == 0.

Return the sum of R[i][j] over all cells.

class Solution {
    int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
    long long bfs(vector<vector<int>>& mat, vector<vector<int>>& vis, int n, int m, int y, int x, int id) {
        long long res = 0;
        queue<pair<int, int>> q;
        auto push = [&](int y, int x) {
            if(vis[y][x] == 0) {
                vis[y][x] = id;
                res += mat[y][x];
                q.push({y,x});
            }
        };
        push(y,x);
        while(q.size()) {
            auto [y,x] = q.front(); q.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 and mat[ny][nx] != -1 and vis[ny][nx] == 0) push(ny,nx);
            }
        }
        return res;
    }
public:
    long long sumRemoteness(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> vis(n,vector<int>(m));
        vector<long long> sums{0};
        long long res = 0, tot = 0;
        for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
            if(grid[i][j] == -1) continue;
            long long now = bfs(grid,vis,n,m,i,j,sums.size());
            sums.push_back(now);
            tot += now;
        }
        for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
            if(grid[i][j] == -1) continue;
            res += tot - sums[vis[i][j]];
        }
        return res;
    }
};