find max squre submatrix

发表于 | 分类于 ， | 阅读次数 |

输入0-1矩阵，返回最大边长的全为1的子矩阵的边长，及在原始矩阵中的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# coding:utf-8
"""
0-1 matrix.
find max squre 1 submatrix.
"""
import numpy as np

def max_squre(matrix):
    # 输入0-1矩阵，返回最大边长的全为1的子矩阵的边长，及在原始矩阵中的位置
    # ms矩阵中i，j处元素：
    # 若不为0, 则代表该处能作为右下角的子矩阵的边长
    w, h = matrix.shape
    ms = np.zeros(shape=(w, h), dtype=np.int8)
    for i in range(w):
        for j in range(h):
            if i == 0 or j == 0:
                ms[i, j] = matrix[i, j]
            else:
                if matrix[i, j] == 1:
                    ms[i, j] = min(ms[i-1, j], ms[i, j-1], ms[i-1, j-1]) + 1
                else:
                    ms[i, j] = 0
    return ms.max(), (ms.argmax()/h, ms.argmax()%h)

def modify(matrix, ms, x, y):
    if matrix[x-ms+1:x+1, y-ms+1:y+1].all():
        # 若子矩阵全为1, 则替换为-1, 显示出来
        matrix[x-ms+1:x+1, y-ms+1:y+1] = -1
    return matrix

def test():
    from random import choice
    n = 15
    for k in range(1):
        matrix = np.zeros(shape=(n, n), dtype=np.int8)
        for (idx, idy), d in np.ndenumerate(matrix):
            matrix[idx, idy] = choice([0, 1])
        ms, (x, y) = max_squre(matrix)
        matrix = modify(matrix, ms, x, y)
        print matrix

if __name__ == "__main__":
    matrix = np.array([
        [0, 0, 1, 1, 1, 0],
        [1, 0, 1, 1, 1, 1],
        [1, 1, 1, 1, 1, 0],
        [0, 1, 1, 0, 1, 1],
        [1, 0, 1, 1, 1, 1],
        [0, 1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1, 1],
        [0, 0, 1, 1, 1, 1],
        [1, 0, 1, 1, 0, 1]
        ])
    ms, (x, y) = max_squre(matrix)
    print ms, x, y
    print modify(matrix, ms, x, y)