競プロのような問題です

Question

入力 1行目：自然数__n__
入力 2行目：0, 1の要素からなる__n__行__n__列の行列

出力：__n__行__n__列の行列の中に含まれる、1のみからなる正方形のうち最大のものの大きさ（辺の数）

例えば、以下のような問題です。

入力：
5
1 1 0 1 0
1 1 0 0 1
0 0 1 1 1
0 1 1 1 1
1 0 1 1 1

出力：
3

上記の例の場合、左上と右下に、1のみからなる正方形があります。
しかし、最大の辺をもつものを知りたいため、答えとしては「3」となります。

以上の問題について、私なりに考えてみたのですが、検討がつきません。

分かる方、いらっしゃいましたら、教えていただきたいです。
よろしくお願いいたします。

Comments

[yambejp]

どこの部分を指して「3」が回答になるのでしょうか？

[dodox86]

制約、例えばnの取り得る値の範囲（最小～最大）があれば示してもらえると良かった。（総当たりで求める場合の計算量に関わるため）　もう閉じた質問なので、良いのですけど。

Answer 1

ある kkサイズの正方形な範囲　が条件（その範囲内の要素が全て1である）を満たすかどうか？　は，
「その範囲内の要素値の総和がkkであるかどうか？」で判定できると思います．
→矩形範囲の総和を計算する方法として，「積分画像 (integral image)」というデータを作って使う方法があります．

一番でかい正方形を見つければよいという話なので，
辺の長さを大きい側から順に調べていく形で，採り得る正方形領域を総当たりしていき，最初に見つけた正方形のサイズが答えになります．

Comments

[white21]

回答ありがとうございます！
もうベストアンサーを選んでしまっていたにもかかわらず、、、すみません。
総和がk*kかどうかで正方形の判定を行うという考え方は、非常にインパクトがありますね。
参考にさせていただきます。

Answer 2

これくらいの数だったら総当たりすればできます。考えられるすべての正方形を列挙し、その中から 1 で埋まっているものを抽出して面積を計算し、その最大値を求めるわけです。

まず左上を頂点とする正方形がいくつあるか、次に左上の一つ右を頂点とする正方形がいくつあるか、という風に考えるところから始めたらどうでしょうか。

Comments

[Zuishin]

それができたら今度は、水平方向と垂直方向に広げながら 0 があった時点で列挙をやめるようにすると時間が短縮されます。

[white21]

なるほど……！
総当たりという手段があることを忘れていました。
スッキリしました。ありがとうございました。