DFS连通性

本文主要是介绍DFS连通性，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

对于连通性，本质上DFS和BFS实际上都可以解决连通块模型

也就是：

1. Flood FIll模型
2. 图和树的遍历

对于连通块模型，BFS除了可以解决是否连通的问题，也可以解决两个点之间最短距离是多少，但是DFS就只能判断两个点是否连通的问题

那这样的话，DFS有什么好处呢？

1. 代码短
2. 直接用系统栈，不需要手写栈

缺点：

​ 当搜索层数很多可能会爆栈

解决迷宫问题

步骤：

1. 从这个点往四个方向出发
2. 判断下一个要到的点的合法性，如果可以就继续递归；如果不行就返回上一层继续搜索

AcWing 1112. 迷宫

// Problem: 迷宫
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1114/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Code by: ING__
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define ll long long
#define re return
#define Endl "\n"
#define endl "\n"

using namespace std;

typedef pair<int, int> PII;

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

int T;
int n;
char mapp[110][110];
bool vis[110][110];

void dfs(int x, int y){
	if(x < 0 || x >= n || y < 0 || y >= n || mapp[x][y] == '#' || vis[x][y]) return;
	vis[x][y] = 1;
	
	for(int i = 0; i < 4; i++){
		dfs(x + dx[i], y + dy[i]);
	}
}

int main(){
	cin >> T;
	while(T--){
		cin >> n;
		for(int i = 0; i < n; i++){
			scanf("%s", mapp[i]);
		}
		int ha, la, hb, lb;
		cin >> ha >> la >> hb >> lb;
		memset(vis, 0, sizeof(vis));
		dfs(ha, la);
		if(vis[hb][lb]){
			cout << "YES" << Endl;
		}
		else cout << "NO" << endl;
	}
	re 0;
}

AcWing 1113. 红与黑

// Problem: 红与黑
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1115/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Code by: ING__
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define ll long long
#define re return
#define Endl "\n"
#define endl "\n"

using namespace std;

typedef pair<int, int> PII;

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

int n, m;
char mapp[25][25];
bool vis[25][25];

int dfs(int x, int y){
	if(x < 0 || x >= n || y < 0 || y >= m || mapp[x][y] == '#' || vis[x][y]) return 0;
	
	int res = 1;
	vis[x][y] = 1;
	for(int i = 0; i < 4; i++){
		res += dfs(x + dx[i], y + dy[i]);
	}
	return res;
}

int main(){
	while(cin >> m >> n, m || n){
		
		for(int i = 0; i < n; i++){
			scanf("%s", mapp[i]);
		}
		
		memset(vis, 0, sizeof(vis));
		
		int x, y;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(mapp[i][j] == '@'){
					x = i;
					y = j;
					break;
				}
			}
		}
		
		cout << dfs(x, y) << endl;
	}
}

这篇关于DFS连通性的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！