acwing算法提高之搜索--DFS连通性模型和搜索顺序

本文主要是介绍acwing算法提高之搜索--DFS连通性模型和搜索顺序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 专题说明

本专题用来记录使用DFS连通性模型或DFS搜索顺序求解的题目。

2 训练

题目1：1112迷宫

考点：dfs

C++代码如下，

#include <iostream>
#include <cstring>using namespace std;//宏定义
#define x first
#define y secondconst int N = 110;
int n;
char g[N][N];
bool st[N][N];
pair<int,int> start_node, end_node;
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};void dfs(int x, int y) {st[x][y] = true;//(x,y)可以走到哪里for (int k = 0; k < 4; ++k) {int nx = x + dirs[k][0];int ny = y + dirs[k][1];if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;if (st[nx][ny]) continue;if (g[nx][ny] == '#') continue;dfs(nx, ny);}return;
}int main() {int T;cin >> T;while (T--) {cin >> n;for (int i = 0; i < n; ++i) cin >> g[i];cin >> start_node.x >> start_node.y >> end_node.x >> end_node.y;memset(st, 0, sizeof st); //每次都要进行重置if (g[start_node.x][start_node.y] == '.' && g[end_node.x][end_node.y] == '.') {dfs(start_node.x, start_node.y);}if (st[end_node.x][end_node.y]) {cout << "YES" << endl;} else {cout << "NO" << endl;}}return 0;
}

这篇关于acwing算法提高之搜索--DFS连通性模型和搜索顺序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---