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/