Как найти дорожные корыта в сетке

Question

У меня есть сетка 9x9 квадратов. Эти квадраты записываются в массив целых чисел. , поэтому каждое целое число представляет собой 1 блок. Integer предоставляет достаточное количество бит для позиций X, Y, если этот блок доступен и другие данные. У меня проблема: что было бы самым эффективным способом получить логическое значение, если мы сможем получить от центра этой сетки до некоторой случайной точки. Так, например, я предоставляю позиции X и Y для блока, куда я хочу идти, и метод вернет логическое значение, если есть какой-то способ через блоки ACCESSIBLE. Я сделал для этого простую картину. Спасибо за ответы.

Answer 1

То, что вы описываете здесь, является известной проблемой в информатике под названием pathfinding и не является тривиальной задачей для эффективного решения.

Однако для решения этой проблемы существует несколько алгоритмов, таких как A* и Dijkstra, которые, вероятно, подходят для больших сложных карт.

Если все ваши проблемы такие же маленькие и простые, как и ваш опубликованный пример, вы также можете попытаться работать с более простым решением, например, методом поиска грубой силы (as suggested by Codor).

Answer 2

Проблема может быть решена depth-first search, где конкретная реализация сильно зависит от представления сетки, которое должно интерпретироваться как graph.