迷宫

题目

信息学奥赛一本通（C++版）在线评测系统 一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由$n\times n$的格点组成，每个格点只有$2$种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

输入

第1行是测试数据的组数$k$，后面跟着$k$组输入。每组测试数据的第$1$行是一个正整数$n(1\le n\le 100)$，表示迷宫的规模是$n\times n$的。接下来是一个$n\times n$的矩阵，矩阵中的元素为.或者#。再接下来一行是$4$个整数$ha,la,hb,lb$，描述A处在第$ha$行, 第$la$列，B处在第$hb$行, 第$lb$列。注意到$ha,la,hb,lb$全部是从$0$开始计数的。

输出

$k$行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。

输入样例

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

输出样例

YES
NO

思路

简单的迷宫深度优先搜索, 这里只需要判断能不能搜到即可, 不需要进行回溯。

代码

const int N = 110;
char g[N][N];
int n, m;
int stX, stY, edX, edY;
bool st[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
 
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;
}
 
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> g[i];
        memset(st, false, sizeof st);
        cin >> stX >> stY >> edX >> edY;
        if (!dfs(stX, stY))
            cout << "NO\n";
        else
            cout << "YES\n";
    }
    return 0;
}