ACWing.1112 迷宫-DFS题解

原题目描述

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。

同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

注意：A、B不一定是两个不同的点。

输入格式

第1行是测试数据的组数 k，后面跟着 k 组输入。

每组测试数据的第1行是一个正整数 n，表示迷宫的规模是 n∗n 的。

接下来是一个 n∗n 的矩阵，矩阵中的元素为.或者#。

再接下来一行是 4 个整数 ha,la,hb,lb，描述 A 处在第 ha 行, 第 la 列，B 处在第 hb 行, 第 lb 列。

注意到 ha,la,hb,lb全部是从 0 开始计数的。

输出格式

k行，每行输出对应一个输入。

能办到则输出“YES”，否则输出“NO”。

数据范围

1≤n≤100

输入样例：

2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0

输出样例:

YES
NO

DFS解题思路

题目给出了由‘#’和‘.’组成的矩阵，可以直接用字符数组储存，也可以在读入的时候转成对应的数字储存在整数数组里，注意n的范围，DFS的过程也很简单，向东西南北递归搜，边界条件写好别溢出就OK

起点和终点的可行性可以单独判断直接输出，不进行DFS

#include <iostream>
using namespace std;

int graph[101][101];
int n = 0;

//把字符图转成数字图储存起来
void get_graph(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            char a;
            cin >> a;
            if(a == '.') graph[i][j] = 1;
            else if(a == '#') graph[i][j] = 0;
        }
    }
}

//爆搜一下，你就知道
bool dfs(int x1, int y1, int x2, int y2){
    graph[x1][y1] = -1;
    if(x1 == x2 && y1 == y2) return true;
    int a[4] = {-1, 0, 1, 0}, b[4] = {0, -1, 0, 1};
    for(int i = 0; i < 4; i++){
        if(x1 + a[i] >= 0 && x1 + a[i] < n && y1 + b[i] >= 0 && y1 + b[i] < n && graph[x1 + a[i]][y1 + b[i]] == 1)
            if(dfs(x1 + a[i], y1 + b[i], x2, y2)) return true;
    }
    graph[x1][y1] = 1;
    return false;
}

//题解
void solve(){
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if(!graph[x1][y1] || !graph[x2][y2]) puts("NO");
    else if(dfs(x1, y1, x2, y2)) puts("YES");
    else puts("NO");
}

int main(){
    int k = 0;
    cin >> k;
    //读入K组数据并给出相应结果
    for(int i = 0; i < k; i++){
        cin >> n;
        get_graph();
        solve();
    }
    return 0;
}