Минимальный ограничивающий прямоугольник массива - PullRequest
Новая
       19

Минимальный ограничивающий прямоугольник массива

0 голосов
/ 04 июля 2018

Проблема заключается в следующем: предоставляется матрица только с 0 и 1 (пример ниже), мне нужно иметь возможность идентифицировать (и в конечном итоге извлечь) минимальный ограничивающий прямоугольник с 1 с.
например, 

0  0 0 0 0  0  
0 [0 0 1 0] 0  
0 [0 1 1 0] 0  
0 [1 0 0 0] 0  
0 [0 0 0 1] 0  
0  0 0 0 0  0

Я не могу найти хорошее решение. Спасибо за вашу помощь!

Ответы [ 3 ]

0 голосов
/ 04 июля 2018 
m = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 1, 1, 0, 0],
    [0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0],
]
min_col = max_col = min_row = max_row = None
for i, row in enumerate(m):
    for j, col in enumerate(row):
        if col:
            if min_row is None:
                min_row = i
            if min_col is None or min_col > j:
                min_col = j
            if max_row is None or max_row < i:
                max_row = i
            if max_col is None or max_col < j:
                max_col = j
print('starting row = %s' % min_row)
print('starting column = %s' % min_col)
print('ending row = %s' % max_row)
print('ending column = %s' % max_col)

Это выводит: 

starting row = 1
starting column = 1
ending row = 4
ending column = 4
0 голосов
/ 04 июля 2018 
arr = [[0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 1, 1, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0]]
# Find all positions where arr value is 1
pos_list = [(i,j) for i,r in enumerate(arr) for j,e in enumerate(r) if e]
# [(1, 3), (2, 2), (2, 3), (3, 1), (4, 4)]

# Get min of all (x, y) values as start_pos and max of all (x, y) values as end_pos
x_pos, y_pos = zip(*[(i,j) for i,r in enumerate(arr) for j,e in enumerate(r) if e])
start_pos, end_pos = (min(x_pos), min(y_pos)), (max(x_pos), max(y_pos))
print (start_pos, end_pos)
# (1, 1), (4, 4)

Удалите все пустые строки, транспонируйте массив (путем его сжатия), снова удалите все строки, транспонируйте его обратно, чтобы получить наименьший вложенный массив для исходного массива, который соответствует всем 1 

sub_arr = list(zip(*[r for r in zip(*[r for r in arr if any(r)]) if any(r)]))
print (sub_arr)
# [(0, 0, 1, 0), (0, 1, 1, 0), (1, 0, 0, 0), (0, 0, 0, 1)]
0 голосов
/ 04 июля 2018

Основная идея:

  • Начните с поля-кандидата, являющегося целым массивом.
  • Хотя первая или последняя строка или первый или последний столбец поля-кандидата содержат только нули, уменьшите поле на эту строку или столбец.
  • Если вы не можете больше сжиматься, следуя этому правилу, у вас есть ограничивающий прямоугольник (возможно, 0 на 0 элементов, если в массиве не было 1).
...