题意描述

给出一个迷宫,求最长的路径

思路

从每个点开始跑bfs 计算每个点可到达的最远点。

解释见代码

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int fx[]={1,-1,0,0},fy[]={0,0,1,-1};
struct node{
    int x,y;
};
int n,m,ans=0;
int d[25][25];
char p[25][25];
bool vis[25][25];
queue<node> q;
int main(){
    memset(p,0x3f,sizeof(p));
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>p[i][j];//输入
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(p[i][j]=='#') continue;//如果这个点是墙 就跳过
            memset(d,0,sizeof(d));//清空两个数组
            memset(vis,0,sizeof(vis));
            q.push((node){i,j});
            vis[i][j]=1;
            while(!q.empty()){//开始bfs 模板
                node no=q.front();
                q.pop();
                for(int k=0;k<4;k++){
                    int nx=no.x+fx[k],ny=no.y+fy[k];
                    if(nx<n&&ny<m&&nx>=0&&ny>=0&&p[nx][ny]=='.'&&!vis[nx][ny]){
                        vis[nx][ny]=1;
                        d[nx][ny]=d[no.x][no.y]+1;
                        ans=max(d[nx][ny],ans);//取最大距离作为答案 这里d每个点都会重置为0
                        q.push((node){nx,ny});
                    }
                }
            }
        }
    }
    printf("%d",ans);//输出答案即可
    return 0;
}