2D range sum and DP and via multi-source 0–1 BFS.

Today I solved an interesting problem. We can use both 2D range sum and DP to solve this problem.

Social Distancing 2

The critical part is converting the problem into find the largest square contains all 0s.

The problem can be solve by using 2D range sum, DP or

2D range sum

int solve(vector<vector<int>>& matrix) {
    const int n = matrix.size();
    if (n<=1) return 0;
    const int m = matrix[0].size();
    for (int j = 1; j < m; ++j)matrix[0][j] += matrix[0][j-1];
    for (int i = 1; i < n; ++i)matrix[i][0] += matrix[i-1][0];
for (int i = 1; i < n; ++i)
        for (int j = 1; j < m; ++j) 
            matrix[i][j] += (matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1]);
    int ret = 0;
    if (matrix[n-1][m-1] == n*m)return 0;
    int len = 1;
    for (int i = 1; i < n; ++i)
    for (int j = 1; j < m; ++j){
        for (int k = len; i + k - 1 < n && j + k - 1 < m; ++k){
            int R = i + k -1, C = j + k - 1;
            int sum =matrix[R][C] - matrix[i-1][C] - matrix[R][j-1] + matrix[i - 1][j - 1];
            if (sum == 0)len = k;
            else break;
        }
    }
return (len + 1 ) / 2; 
}

For the DP and multi-source 0–1 BFS, I will not put the solution here. Please see the discussion session.