---

#include <iostream>

#include <string>

using namespace std;

void path(int x, int y, const int &n, string maze[], int distance[100][100]){

    if(x == n-2 && y == n-2){

        return;

    }

    else {

        if(maze[x+1][y] == '.' && (distance[x+1][y] == 0 || distance[x][y] + 1 < distance[x+1][y])){

            distance[x+1][y] = distance[x][y] + 1;

            path(x+1, y, n, maze, distance);

        }

        if(maze[x][y+1] == '.' && (distance[x][y+1] == 0 || distance[x][y] + 1 < distance[x][y+1])){

            distance[x][y+1] = distance[x][y] + 1;

            path(x, y+1, n, maze, distance);

        }

        if(maze[x-1][y] == '.' && (distance[x-1][y] == 0 || distance[x][y] + 1 < distance[x-1][y])){

            distance[x-1][y] = distance[x][y] + 1;

            path(x-1, y, n, maze, distance);

        }

        if(maze[x][y-1] == '.' && (distance[x][y-1] == 0 || distance[x][y] + 1 < distance[x][y-1])){

            distance[x][y-1] = distance[x][y] + 1;

            path(x, y-1, n, maze, distance);

        }

        if(int(maze[x][y+1] + maze[x+1][y] + maze[x-1][y] + maze[x][y-1]) == (105+46))

            maze[x][y] = '#';

 

    }

    return;

}

int main(int argc, const char * argv[]){

    int n;

    cin>>n;

    string maze[n];

    int distance[100][100] = {0};

    for(int i = 0; i < n; i++)

        cin>>maze[i];

    int x = 1, y = 1;

    path(x, y, n, maze, distance);

    if(distance[n-2][n-2] == 0)

        cout<<"No solution!";

    else

        cout<<distance[n-2][n-2]+1<<endl;

    return 0;

}

我的概念是死路就把'.'變成'#'

創一個相同大小的int陣列儲存走到那一格的最小距離

如果有路可以走，而且(沒有走過或是到這個(x,y)位置的距離+1比下一個存的距離還小)就繼續走

先找往下，再找往左，再找往右，再找往上，如果都沒有就回到上一個點，然後判斷是不是死路。