Итак, вот забавная проблема, с которой я столкнулся, когда решал Nurikabe для моего последнего школьного проекта.
Допустим, у меня есть сетка из n * m плиток, на которых есть препятствия. Теперь представьте, что у меня есть начальная плитка и конечная плитка. Двигаясь только по горизонтали или вертикали, мне нужно добраться от начальной плитки до конечной плитки. Но меня не волнует фактический путь. Все, что мне нужно, это найти пройденные плитки независимо от того, какой путь я бы выбрал.
Белый: пройденные плитки
Серый: препятствия
S: начальный тайл
E: конечный тайл
зеленый: обязательные для прохождения плитки
Надеюсь, этого достаточно, чтобы отобразить то, что я хочу. Я был бы очень признателен, если бы вы могли помочь мне найти лучший алгоритм поиска путей, который можно использовать в этой ситуации, и как я мог бы наиболее эффективно и легко извлекать только обязательные для прохождения плитки.