Список разборов

если добавить исток и сток, ориентировать ребра, то можно найти макс. поток методом Эдмондса Карпа.

Все это займет O(N * M * M) или же по другому O(FM), где F величина потока

Задача на BFS. Сначала находим исходную и конечную точку и направление солдата. Легче будет если создать структуру для солдата(i, j, направление). Добавляем начального солдата в очередь. От каждого солдата(вершины) исходит 4 ребра - менять 3 направление, ...

Воспользуемся стандартным алгоритмом Куна. Описание его работы и реализацию можно найти на emaxx например. http://e-maxx.ru/algo/kuhn_matching

Найдем кратчайшие расстояния от каждой до каждой вершины алгоритмом Флойда. Теперь просто суммируем кратчайшие расстояния всех пар вершин и поделим на кол-во пар вершин (учитывая что пути может и вовсе не быть).

Задача на алгоритм Дейкстры с дополнительными условиями... Первое условие две точки всегда соединены проходом... Второе - через один проход перемещаться одновременно нельзя...

Есть два пути:

1. Реализавывать алгоритм на данном графе и проверять...