# 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.