mxn行列内の最大別の正方行列の数を求める

Question

0または1のいずれかを含むamxn行列があります.2x2の正方形の部分行列が定義されます。この正方行列は元の行列から切り捨てられます。元の行列から切り取ることができるそのような正方行列の最大数を求める。厳密に切断するということは、2つの正方行列が重なり合うことができないことを意味するEXについて - これは、我々が（0,0）から出発して2×2の正方形の部分行列を切断した場合、残りの行列は

0 1 0 
    0 0 0 
1 0 0 0 0 
0 0 0 1 0 
0 0 0 0 0 

さらに2x2の正方サブ行列ができている5×5の行列

0 0 0 1 0 
0 0 0 0 0 
1 0 0 0 0 
0 0 0 1 0 
0 0 0 0 0 

あります この入力では、このような行列を3つまでカットすることができます。

a a 0 1 0 
a a a a 0 
1 0 a a 0 
a a 0 1 0 
a a 0 0 0 

私はバックトラック/再帰的アプローチを試みましたが、それは小さいサイズの入力に対してのみ機能します。誰でももっと効率的なアプローチを提案できますか？

編集：これは、カットできる1つのサブマトリクスであることを示すために、 "a"のマークマトリックス要素を持っています。この行列から計算できる2x2サブ行列（0を含む）の最大数だけを報告する必要があります。

Answer 1

完全性のために、スクリプトを変更していくつかの粗い再帰を行いました。それを行うの再帰的な方法に頼る...

アイデア：Pythonで

f(matrix,count) 
    IF count > length THEN 
     length = count 
    add all options to L 
    IF L is empty THEN 
     return 
    FOR each option in L 
     FOR each position in option 
      set position in matrix to 1 
     f(matrix,count+1) 
     FOR each position in option 
      set position in matrix to 0 

where options are all 2x2 submatrices with only 0s that are currently in matrix 
length = 0 
set M to the matrix with 1s and 0s 
f(M,0) 

：

import copy 

def possibilities(y): 
    l = len(y[0]) # horizontal length of matrix 
    h = len(y) # verticle length of matrix 
    sub = 2 # length of square submatrix you want to shift in this case 2x2 
    length = l-sub+1 
    hieght = h-sub+1 
    x = [[0,0],[0,1], 
     [1,0],[1,1]] 
    # add all 2x2 to list L 
    L=[] 
    for i in range(hieght): 
     for j in range(length): 
      if y[x[0][0]][x[0][1]]==0 and y[x[1][0]][x[1][1]]==0 and y[x[2][0]][x[2][1]]==0 and y[x[3][0]][x[3][1]]==0: 
       # create a copy of x 
       c = copy.deepcopy(x) 
       L.append(c) 
      for k in x: # shift submatrix to the right 1 
       k[1]+=1 
     (x[0][1],x[1][1],x[2][1],x[3][1]) = (0,1,0,1) 
     for k in x: # shift submatrix down 1 
      k[0]+=1 
    return L 



def f(matrix,count): 
    global length 
    if count > length: 
     length = count 
    L = possibilities(matrix) 
    if not L: 
     return 
    for option in L: 
     for position in option: 
      matrix[position[0]][position[1]]=1 
     f(matrix,count+1) 
     # reset back to 0 
     for position in option: 
      matrix[position[0]][position[1]]=0 

length = 0 
# matrix 
M = [[0,0,1,0,0,0], 
    [0,0,0,0,0,0], 
    [1,1,0,0,0,0], 
    [0,1,1,0,0,0]] 
f(M,0) 
print(length)