解法一、BFS

✅ 完整代碼

評分結果(參考) ： AC (2ms, 352KB)

#include<bits/stdc++.h>
using namespace std;

int n, m;

int bfs(vector<string>& maze){
    int pathLen = 0;
    queue<pair<int, int>> q;
    q.push({1, 1});
    maze[1][1] = '-';

    while(!q.empty()){
        int size = q.size();
        while(size-- > 0){
            int i = q.front().first;
            int j = q.front().second;
            q.pop();

            if(i==n-2 && j==m-2){
                return pathLen;
            }

            if(maze[i-1][j]==' '){ q.push({i-1, j}); maze[i-1][j] = '-'; }
            if(maze[i+1][j]==' '){ q.push({i+1, j}); maze[i+1][j] = '-'; }
            if(maze[i][j-1]==' '){ q.push({i, j-1}); maze[i][j-1] = '-'; }
            if(maze[i][j+1]==' '){ q.push({i, j+1}); maze[i][j+1] = '-'; }
        }
        pathLen++;
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    cin.ignore(1, '\n');
    
    vector<string> maze(n);
    for(string& s : maze) getline(cin, s);
    cout << bfs(maze);

    return 0;
}