algorithm - 在 mxn 矩阵中找到最大数量的不同方阵

Question

有一个 m x n 矩阵，其中包含 0 或 1。定义一个 2x2 的方形子矩阵，它只包含 0。如果从原始矩阵中切割出这样的方形子矩阵，那么我们必须找出这样的方形子矩阵的最大数量可以从原始矩阵中切割出来。严格切割意味着没有 2 方子矩阵可以重叠。对于前 -这是一个 5x5 矩阵

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  

如果我们从 (0,0) 开始切割一个 2x2 的方形子矩阵，那么剩下的矩阵是

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

可以切割进一步的2x2方形子矩阵在此给定输入中，最多可以切割 3 个这样的矩阵。如果我用 'a' 标记它们

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  

我已经尝试过回溯/递归方法，但它只能用于较小的输入。有人可以建议更有效的方法吗？

编辑:我用“a”标记矩阵元素以表明这是一个可以切割的子矩阵。我们只需要报告可以从此矩阵中获取的 2x2 子矩阵(包含全 0)的最大数量

Answer 1

为了完整起见，我更改了脚本以进行一些粗略的递归，你是对的，很难不求助于递归方式...

想法:

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)

在 python 中:

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)