B. Bargaining Table
time limit per test
memory limit per test
input
output
Bob wants to put a new bargaining table in his office. To do so he measured the office room thoroughly and drew its plan: Bob's office room is a rectangular room n × m
Input
The first line contains 2 space-separated numbers n and m (1 ≤ n, m ≤ 25) — the office room dimensions. Then there follow n lines withm
Output
Output one number — the maximum possible perimeter of a bargaining table for Bob's office room.
Examples
input
3 3
000
010
000
output
8
input
5 4
1100
0000
0000
0000
0000
output
16
用dp[i][j]表示左上角为(1, 1)右下角为(i,j)的矩形里有多少个1, dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1];如果(i,j)本身是1则dp[i][j]++;
遍历每个点(i,j)如果str[i][j] == '0'则把(i,j)表示矩阵的右下角枚举矩阵的左下角(i, h1)和右上角(h2, j)首先判断这个矩阵内1的数目 = dp[i][j] - dp[i][h1-1] - dp[h2-1][j] + dp[h2-1][h1-1]， 如果矩阵内没有1则可算矩阵的周长
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
typedef long long ll;
char str[30][30];
int dp[30][30];
int main(){
// freopen("in.txt", "r", stdin);
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%s", str[i]+1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
if(str[i][j] == '1')
dp[i][j] = 1;
dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
}
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
if(str[i][j] == '1')
continue;
for(int h1 = i-1; h1 >= 0; h1--){
for(int h2 = j-1; h2 >= 0; h2--){
int d = dp[i][j] - dp[h1][j] - dp[i][h2] + dp[h1][h2];
if(d == 0){
ans = max(ans, 2 * (i - h1 + j - h2));
}
if(str[i][h2] == '1')
break;
}
if(str[h1][j] == '1')
break;
}
}
printf("%d\n", ans);
return 0;
}