[HOJ 164][POI 18 Stage 1]森森砍你的臉

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

這題我用O(N^3)的做法，然後過了OAO
總之，記錄每一點往右和往下最多連續幾個1，然後枚舉正方形的左上角，接著枚舉邊長，正方形存在答案就+1
最後幾筆1200ms左右，時限1500ms...
後來有寫出O(N^2logN)的作法

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
int N,DOWN[1000][1000],RIGHT[1000][1000];
char GRID[1000][1000];
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)
    {
        char &c=GRID[i][j];
        do{c=getchar();}while(c!='0'&&c!='1');
    }
    for(int i=N-1;i>=0;i--)for(int j=N-1;j>=0;j--)
    {
        if(GRID[i][j]=='0')DOWN[i][j]=RIGHT[i][j]=0;
        else DOWN[i][j]=(i==N-1?1:DOWN[i+1][j]+1),RIGHT[i][j]=(j==N-1?1:RIGHT[i][j+1]+1);
    }
    int ans=0;
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)
    {
        int mxlen=min(DOWN[i][j],RIGHT[i][j]);
        for(int len=1;len<=mxlen;len++)if(DOWN[i][j+len-1]>=len&&RIGHT[i+len-1][j]>=len)ans++;
    }
    printf("%d\n",ans);
    return 0;
}