D. Кратчайший путь по карте

Дана карта из символов . (проходимо) и # (стена). Найдите длину кратчайшего пути из левой верхней клетки в правую нижнюю, двигаясь по проходимым клеткам вверх, вниз, влево и вправо.

Длина пути — количество шагов. Если стартовая или конечная клетка занята стеной, пути нет.

На прошлом занятии похожая задача решалась обходом в глубину — но там спрашивалось только, есть ли путь. Как только спросили про длину, обход в глубину перестаёт годиться.

Первая строка содержит числа $n$ и $m$ ($1 \le n, m \le 1000$).

Далее идут $n$ строк по $m$ символов.

Одно число — длина кратчайшего пути или $-1$.