官方题解

题目大意

有一个 $n\times m$ 的迷宫，有 . 和 # 两种图形， # 表示障碍物，. 表示可以走的路。起点为 $(1,1)$ 每次只能向下或向右走，问当无法移动时，最多可以经过多少个格子。

解题思路

使用 $bfs$ 进行二方向遍历，并用距离数组 $d$ 记录从起点到每个点的所经过的格子数。最终取 $d$ 数组的最大值即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

char g[N][N];
int d[N][N];
bool vis[N][N];

int dx[2] = {0, 1}, dy[2] = {1, 0};

int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }

    queue<pair<int,int>>q;
    q.push({1,1});
    vis[1][1]=true;
    d[1][1]=1;
    while(!q.empty()){
        auto [x,y]=q.front();q.pop();

        for(int i=0;i<2;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny] || g[nx][ny]=='#') continue;

            q.push({nx,ny});
            d[nx][ny]=d[x][y]+1;
            vis[nx][ny]=true;
        }
    }
    
    int res=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            res=max(res,d[i][j]);
        }
    }
    cout<<res<<endl;
    return 0;
}