Вам надо построить хитрый граф.
Во-первых, все расстояния в графе будут не одно число, а пара - собственно, длина пути и количество поворотов. При суммировании двух длин складывайте их покомпонентно, при сравнении сравнивайте сначала длины, а потом количество поворотов. Теоретически, можно схлопнуть все назад в одно число, если считать 100000*<длина> + <количество поворотов>. Но могут быть спецэффекты, если пути очень сложные и имеюют более 100000 поворотов. Еще, опасайтесь переполнения.
Для каждой клетки сделайте 4 вершины, которые будут означать, что вы находитесь в этой клетке и "смотрите" в одну из 4-х сторон.
Создайте 4 ребера между соседними направлениями с длиной {0, 1} (длина 0, но 1 поворот). От каждой вершины создайте также ребро длинной {1, 0} (длина - 1, 0 поворотов) в вершину в соседней клетке с тем же направлением (от "верхней" из 4-х вершин сделайте ребро в "верхнюю" же вершину в клетке сверху. Аналогично по трем остальным направлениям).
Теперь кратчайший путь в этом графе будет то - что вам надо. Есть еще вопрос с начальными конечным направлением. Можно добавить в начальную и конечную клетки "центральную" вершину, в которая связанна ребрами длины {0, 1} (Важно сделать 1 поворот, иначе можно будет крутиться на месте через эту центральную вершину). Считайте, что эта вершина - "смотреть в пол". Вы начинаете в какой-то клетке, смотря в пол, и вам надо оказаться в другой клетке, опять же смотря в пол. Вы можете в клетке повернуться, или перейти в клетку впереди вас.
Поскольку тут уже разные длины ребер, обход в ширину уже не будет искать кратчайшее расстояние. Но можно использовать дейкстру/A*.
При реализации не надо даже хранить все вершины и ребра. Просто у вас теперь вершина вместо {x, y} будет описываться {x, y, d}. Вместо перебора 4-х направлений [-1,0],[0,-1],[0,1],[1,0] - вы делаете переход {x+dx[d],y+dy[d],d} или меняете d на (d+1)%d и (d+3)%4. И в очередях вы сохраняете не одно число, а пару {length, turns}. Для A* нужно еще прикидывать оставшуюся длину - ну вы по длине берите, что у вас уже есть, а по количеству поворотов берите 1, если у начала и конца разные направления.
Играясь с длинами ребер и их сравнениями вы можете, например, разрешать чуть более длинные пути, если в них сильно меньше поворотов. (например, можно обойти лабиринт по периметру, чем чуть короче но зиг-загами ходить внутри). Для этого длина ребра может быть length*K+turns.
Поскольку тут в 4-5 раз больше вершин, это будет работать в 4-5 раз медленнее.
Средний
