Самое простое - это сделать вершиной каждую клетку и гнать в этом графе поиск в ширину. Можно даже не строить граф явно - а просто при обходе смотреть на четырех соседей и проверять, а не стена ли там, а были ли мы в клетке (x+dx[k], y+dy[k]), и класть координаты в очередь, если надо.
Вы же хотите считать только перекрестки и повороты врешинами. В худшем случае, если поворотов в лабиринте много - это будет даже медленнее обхода в ширину. Потому что он работает за линию, а дейкстра - за O(n log n) в лучшем случае. Плюс там константа больше у этого n log n. Правда, это можно решить если вместо дейкстры использовать обобщенный 0-1-BFS (BFS с ограниченными ребрами - там где много очередей используется). Но реализация будет сильно посложнее простого BFS.
Но если так хотите - то делается это так: Сначала пройдитесь по всем клеткам и занумеруйте те, которые не являются коридором (один сосед, больше двух соседей, или соседи не вдоль одной прямой). Можно в отдельной матрице номера проставить.
Потом пройдитесь по каждому столбцу сверху вниз и по каждой строчке слева направо и храните последнюю встреченную вершину. Если встретили стену - забывайте про эту увиденную раньше врешину. Если встретили просто проход - пропускайте его. Если встретили поворот(вершину) - то создайте ребро между ней и последней увиденной (если она еще в памяти, ведь стена могла ее удалить). Ну и перепишите последнюю увиденную вершину.
Что-то типа такого:
int last_node = 0;
for (i = x_start, j = y_start; i <n && j < m; i+= dx, j+=dy) {
if (is_wall[i][j]) {
last_node = -1;
}
if (node_number[i][j] <- 0) continue;
if (last_node > 0) {
// добавить ребро между вершинами.
AddEdge(last_node, node_number[i][j]);
}
last_node = node_number[i][j];
}
Тут я просто добавляю ребра в строке или столбце между двумя соседними вершинами.
Средний
