Алгоритм - цвет окружен другим цветом в матрице - PullRequest
Новая
       33

Алгоритм - цвет окружен другим цветом в матрице

3 голосов
/ 03 февраля 2020

Я недавно столкнулся с этой проблемой в интервью:

Приведенная ниже матрица: 

[[ R R R R R R],
 [ R B B B R R],
 [ B R R R B B],
 [ R B R R R R]]

Узнайте, есть ли в любой группе только R * или только B, окруженные противоположным цветом, в четырех направлениях: вверх, вниз, влево, вправо.

ex: Ответ на приведенную выше матрицу -> Допустимый набор B, окруженный R во втором ряду. 

[[ R R R R R R],
 [ R **B B B** R R],
 [ B R R R B B],
 [ R B R R R R]]

Я пытался сделать BFS для определенного c цвета во всех направлениях, но не смог найти решение. Может кто-нибудь направить меня к решению.

1 Ответ

1 голос
/ 03 февраля 2020

Чтобы найти группы B-ячеек, окруженных R-ячейками, представьте себе матрицу как граф, вершинами которого являются все B-ячейки с ребрами, соединяющими соседние B-ячейки. Используйте BFS (или DFS), чтобы найти связанных компонентов этого графика, но игнорируйте связанные компоненты, которые содержат ячейки на границе. Каждый (не граничный) связанный компонент содержит набор B-ячеек, окруженных R-ячеями. Затем, чтобы найти группы R-ячеек, окруженных B-ячейками, аналогичным образом вычислите не граничные связные компоненты графа, вершинами которых являются R-ячейки.

Поскольку число вершин и ребер обоих графов равно O(mn) и набор связанных компонентов графика может быть найден во времени, которое является линейным по размеру графика, время работы этого алгоритма равно O(mn).

...