寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C++ #DPL_3_A : Largest Square

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題 "Largest Square"
https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_A
・最大正方形

僕が作成、提出したコードは、以下のとおりです。

Aizu Online Judge in C++ #DPL_3_A : Largest Square
/*
Aizu Online Judge in C++ #DPL_3_A : Largest Square
https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_A
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
const int m=1401;
int g[m][m]={0};
int h,w;
int dp[m][m]={0};
int f(void){
    int maximum=0;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(g[i][j]==1){
                dp[i][j]=0;
            }else{
                dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
            }
            maximum=max(maximum,dp[i][j]);
        }
    }
    return maximum*maximum;
}
int main(void){
    cin>>h>>w;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>g[i][j];
        }
    }
    cout<<f()<<endl;
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/