Codeforces 22 B. Bargaining Table 做题记录

　　其实是比较基础的模拟（$n<=25$），写个$O(n^4)$的暴力就过了。感觉可以用倍增优化一下，可以但没必要。 　　……太菜了还挂了几发。反思一下，一个是写函数改来改去int类型没返回值，本地编译器可以正常运行，但是好像codeforces会T。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=25;

int n,m;
char str[maxn+5];
int room[maxn+5][maxn+5];
int sum[maxn+5][maxn+5];

bool check(int x1,int y1,int x2,int y2){
    return (sum[x2][y2]+sum[x1-1][y1-1]-sum[x2][y1-1]-sum[x1-1][y2])>0?1:0;
}
int perimeter(int x1,int y1,int x2,int y2){
    return ((x2-x1+1)+(y2-y1+1))<<1;
}

int ans;
void maxsize(int x,int y){
    // [x-i][y-j] 
    int now=0;
    for (int i=0,j=y-1;i<x;i++){
        while (j>=0&&check(x-i,y-j,x,y)){
            if (perimeter(x-i,y-j,x,y)<ans)
                break;
            j--;
        }
        if (j>=0&&perimeter(x-i,y-j,x,y)>ans)
            ans=perimeter(x-i,y-j,x,y);
        if (j<0)
            break;
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%s",str);
        for (int j=1;j<=m;j++){
            room[i][j]=str[j-1]-'0';
            sum[i][j]=room[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (room[i][j]==0)
                maxsize(i,j);
    printf("%d",ans);
    return 0;
}