алгоритм поиска пустых ячеек в тральщике

Question

Я создаю тральщик и просто задаюсь вопросом, каков наилучший алгоритм для поиска всех пустых ячеек, когда пользователь нажимает пустую ячейку, затем растёт и ограничивается границей, пока не достигнет ячейки бомбы. Я планирую использовать рекурсивный поиск, но, вероятно, это замедлит процесс.

Спасибо.

Answer 1

Если вы графически изображаете обнаружение, я бы сказал, что было бы лучше сделать это в несколько шагов (увеличьте границу, как вы предлагаете):

1. Раскрыть квадрат, на который нажали, найти все находящиеся поблизости записи, которые явно обрабатываются.
2. Откройте эти квадраты, найдите все записи рядом с теми, которые явно обрабатываются.
3. Повторите с шага 2.

Таким образом, пользователь может видеть это, что всегда хорошо. Смешайте анимацию, и это может быть что-то классное, что заставляет кого-то надеяться на это.

Answer 2

Решение Epsilon Prime - хороший способ реализовать его.

Вы можете сделать это с очередью .

Пример:

push the first empty cell/point
LOOP until queue non empty 
   pop.head cell and reveal it
   push the empty surrounding cells of it (8 at maximum)
     (you must flag the cells so you don't push them again,  
      ie dont push the cells that are already revealed)

Answer 3

С алгоритмической точки зрения вы не ошибетесь с Поиск в ширину или Поиск в глубину . Ответ Ника D в основном описывает поиск в ширину, но в целом решение, которое вы хотите, будет "пока вы все еще смотрите на квадраты, покажите квадрат; если у квадрата нет соседей по бомбе, то для каждого из восьми соседей, которые еще не посещены, пометьте их как посещенных и добавьте их в список квадратов, на которые вы просматриваете ". повторяйте это до тех пор, пока список квадратов, на которые вы смотрите, не станут пустыми, и начните с квадрата, который нажимает пользователь.