1112. 迷宫

1112. 迷宫 - AcWing题库

这个题比正常的深搜题有点点不一样，区别在于在递归中不需要回溯。即是只需要记录是否走过，不用去掉标记。

思路没有什么好说的，直接来看一下代码即可：

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int T;

int n;
char g[N][N];
bool st[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int stx, sty, edx, edy;

bool dfs (int x, int y) 
{
    if (g[x][y] == '#') return false;
    if (x == edx && y == edy) return true;
    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 >= n) continue;
        if (st[a][b]) continue;
        if (dfs(a, b)) return true;
    }

    return false;
}

void slove() {
    memset(st, false, sizeof st);
    cin >> n;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ ) {
            cin >> g[i][j];
        }

    cin >> stx >> sty >> edx >> edy;

    if (dfs(stx, sty)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return ;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;

    while (T -- ) {
        slove();
    }
}