本文主要是介绍搜索专项---DFS之连通性模型，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 迷宫
- 红与黑
一、迷宫OJ链接
本题思路:DFS直接搜即可。
#include <iostream>
#include <cstring>
#include <algorithm>constexpr int N=110;int n;
char g[N][N];
bool st[N][N];
int x1, y1, x2, y2;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};bool dfs(int x,int y)
{if(x==x2&&y==y2) return true;st[x][y]=true;if(g[x][y]=='#') return false;for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(st[a][b]) continue;if(a<0||a>=n||b<0||b>=n) continue;if(dfs(a,b)) return true;}return false;
}
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T;std::cin>>T;while(T--){std::cin>>n;for(int i=0;i<n;i++) std::cin>>g[i];memset(st,0,sizeof st);std::cin>>x1>>y1>>x2>>y2;if(g[x1][y1]=='#'||g[x2][y2]=='#'){std::cout<<"NO"<<std::endl;continue;}if(dfs(x1,y1)) std::cout<<"YES"<<std::endl;else std::cout<<"NO"<<std::endl;}return 0;
}二、红与黑OJ链接
本题思路:类似于岛屿问题。
#include <bits/stdc++.h>constexpr int N=25;int n,m;
char g[N][N];
bool st[N][N];int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int dfs(int x,int y)
{int cnt=1;st[x][y]=true;for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if (a < 0 || a >= n || b < 0 || b >= m) continue;if (g[a][b] != '.') continue;if (st[a][b]) continue;cnt+=dfs(a,b);}return cnt;
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);while(std::cin>>m>>n,m||n){for(int i=0;i<n;i++) std::cin>>g[i];int x,y;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='@'){x=i;y=j;}memset(st, 0, sizeof st);std::cout<<dfs(x,y)<<std::endl;}return 0;
}这篇关于搜索专项---DFS之连通性模型的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
