GeeksforGeeks(最大正方形)

[GeeksforGeeks,DP]

GeeksforGeeks(最大正方形)

• 翻訳元
  • Maximum size square sub-matrix with all 1s

• 練習問題
  • AOJ - Pattern - Largest Square

サイズがすべて１の正方形の部分行列の最大値

２進値をもつ行列（以下、二値行列）を考える、値としてすべて１を含む入れ子の行列の最大の大きさを求めよ。

例えば、以下のような二値行列を考える：

  アルゴリズム

発想

• 二値行列を M[R][C] とします。アルゴリズムの発想は、S[][]という補助的な行列を構築することです。
• その行列では、S[i][j]はM[i][j]を含むすべて１で構成される正方形の部分行列の大きさを表す。
  • そこではM[i][j]は部分行列の最も右下にあるものも含む。

手順

• (1) M[R][C]からS[R][C]という合計値を含む行列を構築する。
  • (a) 最初の行とと最初の列をM[][]からS[][]にコピーする
  • (b) 他のすべての要素に対して、S[][]を構築するために以下の処理を使う

         If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0

• (2) S[R][C]から最大の要素を見つける
• (3) その値とS[i]の最大要素の座標を使って、M[][]の部分行列を出力する

上の例では所与のM[R][C]によって構築されたS[R][C]は以下のようになる：

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  0
   1  2  2  3  1
   0  0  0  0  0

上記の行列の最大値は３で座標は(4, 3)である。その最大値と座標を使って、これにより題意を満たす部分行列を求められた。

  サンプルコード

#
# Ruby code for Maximum size square sub-matrix with all 1s
#
def print_max_sub_square(m)
  row,col = m.size, m.first.size
  s = Array.new(row){Array.new(col,0)}

  # Set first column of S[][]
  for i in 0...row
    s[i][0] = m[i][0]
  end
  # Set first row of S[][]
  for j in 0...col
    s[0][j] = m[0][j]
  end

  # Construct other entries of S[][]
  for i in 1...row
    for j in 1...col
      if m[i][j] == 1
        s[i][j] = [ s[i][j-1], s[i-1][j], s[i-1][j-1] ].min + 1
      else
        s[i][j] = 0
      end
    end
  end
  # Find the maximum entry, and indexes of maximum entry in S[][]
  max_of_s,max_i,max_j = s[0][0],0,0

  for i in 0...row
    for j in 0...col
      if max_of_s < s[i][j]
        max_of_s,max_i,max_j = s[i][j],i,j
      end
    end
  end

  printf "Maximum size sub-matrix is: \n"
  max_i.downto(max_i - max_of_s + 1) do |i|
    max_j.downto(max_j - max_of_s + 1) do |j|
      printf "%d", m[i][j]
    end
    puts ""
  end
end

# Driver function to test above functions
M = [
  [0, 1, 1, 0, 1],
  [1, 1, 0, 1, 0],
  [0, 1, 1, 1, 0],
  [1, 1, 1, 1, 0],
  [1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0]
]

print_max_sub_square(M)

 Maximum size sub-matrix is: 
 111
 111
 111

• 時間計算量： O(m*n) 、所与の行列においてmは行数そしてnは列数
• 空間計算量： O(m*n) 、所与の行列においてmは行数そしてnは列数

  考察

• 漸化式
  • dp[i][j] = \begin{eqnarray} \left\{ \begin{array}{l} 0 (M[i][j] != 1) \\ min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1\end{array} \right. \end{eqnarray}

• こんな感じ？
  • [ ] で囲んだのが　⇛　dp[i][j-1], dp[i-1][j], dp[i-1][j-1]
  • ( ) で囲んだのが　⇛　dp[i][j]

これにより、S[R][C]のそれぞれの座標に最大の大きさの正方形の辺の長さが格納される

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  0
   1  2  2  3  1
   0  0  0  0  0