Алгоритм: Определить форму двух секторов очерченных по произвольному пути, а затем заполнить один

Question

ПРИМЕЧАНИЕ: Это сложная проблема для тех, кто любит логические проблемы и т.д.

Рассмотрим прямоугольную двумерную сетку высоты Н и шириной W. Каждое пространство в сетке имеет значение, либо 01, либо 2. Первоначально каждое место на сетке является 0, за исключением пространств вдоль каждого из четырех ребер, изначально из которых 2.

Затем рассмотрите произвольный путь соседних (по горизонтали или вертикали) пространств сетки. Путь начинается на 2 и заканчивается на другом 2. Каждое пространство вдоль пути - 1.

Путь делит сетку на два «сектора» 0. Существует объект, который опирается на неуказанное пространство 0. «Сектор», который НЕ содержит объект, должен быть полностью заполнен 2.

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

После того, как алгоритм завершится, и пустой «сектор» заполнен полностью 2 s, алгоритм SAME должен быть достаточным, чтобы повторить тот же процесс. Второе (и время), путь по-прежнему оттягивается от 2 до другого 2 через пробелы 0, но «сетка» меньше, потому что 2 s, которые окружены другими 2 с, не могут быть затронуты путем (так как путь проходит вдоль пространств 0).

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

Answer 1

Кажется мне основной flood fill алгоритма будет получить работу:

• Проверьте ваш массив в первый 0 вы найдете, а затем начать заливку оттуда, заполняя 0 области с другим номером , скажем, 3 - это будет обозначать один из ваших «секторов».
• Как только это будет сделано, сканируйте еще раз на 0 и заполните заливку оттуда, заполнив 4 на этот раз.
• Во время обоих заливок вы можете проверить, находили ли вы свой объект или нет; в зависимости от того, что вы наберете, вовремя, отслеживайте это число.
• После того, как оба заливки закончены, проверьте, в какой нумерованной области был объект в нем - заливка заполняет эту область снова, назад с 0 на этот раз.
• Наводнение заполняет другую пронумерованную область 2, и все готово.

Это будет работать для любой конфигурации сетки, если существует ровно два сектора 0, которые отключены друг от друга; поэтому повторное применение одного и того же алгоритма выполняется в любое время.

Edit: Мелкие хитрости, чтобы спасти вас от наводнения заливку или два -

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