Блог

У меня есть матрица:

 5 5 1 4 4
4 0 2 4 2
5 0 0 2 0
5 4 3 0 1
1 3 3 2 1
  

Как вы можете видеть, в матрице есть области с нулями. Для области нуля, подобной лестнице (посмотрите на координаты (1, 1)(2, 1)(2, 2) . Это заключено в

• 0 области с цифрой 1
• 1 области с цифрой 2
• 1 области с цифрой 3
• 2 области с цифрой 4
• 2 области с цифрой 5

Суть в том, что область цифр может быть непрерывной, если соседний элемент имеет то же значение.

Например, посмотрите на ближайшую 5 к нулевой области по координате (0, 1) . У него есть сосед с координатой (0, 0) . Также вторая 5 область, расположенная от (2, 0) координаты, имеет соседа (3, 0) . Итак, всего у нас есть две 5 области с координатами (0, 1), (0, 0), (2, 0), (3, 0) , и, таким образом, длина 5 области для этой нулевой области равна 4 !

3 Are имеет длину 3 (она начинается с (3, 2) и переходит в (4, 2) , а затем в (4, 1) . Суть в том, чтобы заменить элементы нулевой области (т. Е. Все нули внутри) на значения в диапазоне 1, 2, 3, 4, 5 , где соответствующая область цифр имеет наибольшую длину. В нашем случае все нули заменяются на 5 . То же самое делается с другими нулевыми областями.

Вопрос в том, какой алгоритм я должен использовать?Единственной идеей, которая пришла мне в голову, было создать какой-нибудь огромный картографический словарь и каким-то образом искать пересечения координат и изменять состояния, но это было неправильно. Я больше не знаю, как решить эту проблему!

Мой подход

• Сначала используйте DFS или BFS для идентификации непрерывных областей с одинаковыми цифрами. Это можно сделать с помощью
  • Посетите каждую ячейку (в любом порядке, например, сверху вниз, слева направо)
  • Если посещенная ячейка не была отмечена как принадлежащая известным непрерывным областям, запустите DFS или BFS, начиная с этой ячейки, и подключитесь к соседним ячейкам, имеющим цифры, затем пометьте все ячейки, посещенные DFS / BFS, как новые области
  • Если посещенная ячейка была отмечена, просто перейдите к следующей ячейке
• После завершения всех DFS / BFS у вас будет карта из каждой ячейки в каждую уникальную область. Например, области будут сегментированы, как показано ниже (я буду использовать алфавиты для обозначения областей, чтобы избежать путаницы с цифрами, но на самом деле вы также можете использовать целые числа для обозначения областей)

 a a b c c
d e f g h
i e e j k
i l m n o
p m m q o
  

• Вы также должны вычислить длину каждой области: area_len = {a: 2, b: 1, c: 2, etc...} , и набор областей, связанных с 0: zero_areas = {e, k, n}
• Далее вам нужно построить набор соседних областей нулей, связанных с каждой цифрой : D[i] = set of neighour of zeros associated with digits i . Например, D[5] = {a, i}, D[1] = {o} .
  • Это можно сделать, перебрав все ячейки в нулевых областях и просмотрев всех соседей таких ячеек

 for area in zero_areas:
   for cell in area:
      for neighbour_cell in neighbours of cell:
          add area of neighbour_cell to D[digit of neighbour_cell]
  

• Наконец, для каждой цифры i вычислите сумму длины области в D[i] и выберите наибольшую.

Временная сложность = сложность DFS / BFS размер нулевых областей = O (M), где M — количество элементов в матрице = O (N ^ 2), где N — строки и столбцы матрицы