Алгоритм: определить форму двух секторов, обозначенных произвольным путем, а затем заполнить один - PullRequest
Новая
       18

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

2 голосов
/ 16 мая 2010

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

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

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

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

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

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

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

1 Ответ

3 голосов
/ 16 мая 2010

Мне кажется, базовый флуд-заполнитель алгоритм выполнит свою работу:

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

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

Редактировать: Незначительные изменения, чтобы спасти вас от наводнения или два -

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