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

Data Scientist/MLE/SWE @takemobi