有一个 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)的最大数量
最佳答案
为了完整起见,我更改了脚本以进行一些粗略的递归,你是对的,很难不求助于递归方式...
想法:
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)
关于algorithm - 在 mxn 矩阵中找到最大数量的不同方阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38903180/