1 专题说明

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

2 训练

题目1：1112迷宫

考点：dfs

C++代码如下，

#include <iostream>
#include <cstring>

using namespace std;

//宏定义
#define x first
#define y second

const 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;
}