BFS 可以求得最短路, DFS 会找到从当前点到图中叶子结点的路径.
- #define HAVE_STRUCT_TIMESPEC
- #include<bits/stdc++.h>
- using namespace std;
- int n,m,ans;
- char s[25][25];
- bool vis[25][25];
- struct node{
- int x,y,dis;
- };
- int direction[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
- void bfs(int x,int y){
- if(s[x][y]=='#')
- return ;
- memset(vis,0,sizeof(vis));
- queue<node>q;
- q.push((node){x,y,0});
- vis[x][y]=1;
- while(!q.empty()){
- node now=q.front();
- q.pop();
- ans=max(ans,now.dis);
- for(int i=0;i<4;++i){
- int temp_x=now.x+direction[i][0],temp_y=now.y+direction[i][1];
- if(temp_x<=0||temp_x>n||temp_y<=0||temp_y>m||s[temp_x][temp_y]=='#'||vis[temp_x][temp_y])
- continue;
- q.push((node){temp_x,temp_y,now.dis+1});
- vis[temp_x][temp_y]=1;
- }
- }
- }
- int main(){
- iOS::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- cin>>n>>m;
- for(int i=1;i<=n;++i)
- cin>>s[i]+1;
- for(int i=1;i<=n;++i)
- for(int j=1;j<=m;++j)
- bfs(i,j);
- cout<<ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3379257.html