TIOJ1097 營地

題幹：

給一個0,1,2組成的平面

求0組成的最大正方形

連結：https://tioj.ck.tp.edu.tw/problems/1097

題解：

當時看到覺得頗神奇

建表當遇到０算1遇其他則算0

dp(i,j)=max(dp(i-1,j),dp(i,j-1),dp(i-1,j-1))

空間限制要滾一下

#include <iostream>

#include <algorithm>

using namespace std;

int d[2][5005];

int main() {

    int m,n,t,mx;

    while(scanf("%d%d",&m,&n)==2&&m&&n){

        mx=0;

        for(int i=0;i<n;i++) {

            cin>>t;

            d[0][i]=t==2?0:1;

            if(t!=2)mx=1;

        }

        for(int i=1;i<m;i++){

            cin>>t;

            d[1][0]=t==2?0:1;

            for(int j=1;j<n;j++){

                cin>>t;

                if(t==2)d[1][j]=0;

                else {

                    d[1][j]=min(d[0][j-1],min(d[0][j],d[1][j-1]))+1;

                    mx=max(d[1][j],mx);

                }

            }

            for(int i=0;i<n;i++) //滾動

                d[0][i]=d[1][i];

        }

        cout<<mx*mx<<endl;

    }

    return 0;

}