Похоже, тут обычный поиск в ширину. Сначала находишь первую вершину (просмотреть первую строку, потом вторую и т.д., первая попавшаяся звездочка будет поворотом или тупиком). Ну а далее все соседние звездочки - это соседние вершины, либо пути в соседние вершины (то есть в каждую сторону идешь прямо, пока встречаются "транзитные" звездочки, а именно ограниченные решетками или краями карты с двух противоположных сторон, и подсчитываешь длину пути).
Если в лабиринте только одно пространство, то обойдешь всё. Иначе надо после завершения обхода в ширину снова искать неотмеченные вершины.
