AOJ 0092: Square Searching

問題

Square Searching | Aizu Online Judge
0,1（.,*）でできたn*nのマス目が与えらえるので、0で作れる最大の正方形のサイズを求める
$1 \le n \le 1000$

解法

愚直にやると$O(n^3)$でTLE。
以下のようなDPを考えることで$O(n^2)$になる。

あるマス（図中の赤文字の0）について、以下３要素（図中の青枠）のうち一番小さい数が、そのマスを右下として作れる最大の正方形のサイズ（図中の赤枠）である。

• マスから上に0が続く数
• マスから左に0が続く数
• 一つ左上のマスでできる最大の正方形サイズ+1

よって、上記３要素をそれぞれDP配列（n*n）に左上から埋めていけばよい。

DP配列を左上から右下に埋めていくとすると1行上（上に0が続く数、左上の最大サイズ）と1マス左（左に0が続く数）しか参照しないので、
実装では1行上＋1マス左しか保持しなくてすむ。

while(n=gets.to_i)>0
  dp=[[0,0]]*n
  r=0...n
  p r.map{
    s=gets
    w=0
    (dp=r.map{|j|
      h,w=s[j]<?.?[0,0]:[d[j][0]+1,w+1]
      [h,[h,w,dp[j-1][1]+1].min]
    }).map{|h,s|s}.max
  }.max
end