<—点个赞吧QwQ

宣传一下算法提高课整理

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

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

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

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

输入格式

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

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

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

再接下来一行是 4 个整数 $h_a, l_a, h_b, l_b$，描述 $A$ 处在第 $h_a$ 行, 第 $l_a$ 列，$B$ 处在第 $h_b$ 行, 第 $l_b$ 列。

注意到 $h_a, l_a, h_b, l_b$ 全部是从 0 开始计数的。

输出格式

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

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

数据范围

$1 \le n \le 100$

输入样例：

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

输出样例:

YES
NO

思路1

我们直接用迷宫问题的思路来解决这题。
我们只需要把求得距离改成是否到达过这个点即可。
$\text{DFS}$代码：

代码1

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
const int dx[] = {0,-1,0,1},dy[] = {-1,0,1,0};
int n;
int sx,sy,ex,ey;
int g[N][N];
bool st[N][N];
bool dfs (int x,int y) {
    if (x == ex && y == ey)return true;
    st[x][y] = true;
    for(int i = 0;i < 4;i++) {
        int a = x + dx[i], b = y + dy[i];
        if(a < 1 || a > n || b < 1 || b > n) continue;
        if (g[a][b] == 1 || st[a][b]) continue;
        if (dfs(a,b)) return true;
    }
    return false;
}
int main () {
    int T;
    cin >> T;
    while (T--) {
        memset (st,false,sizeof (st));
        cin >> n;
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                char ch;
                cin >> ch;
                if (ch == '#') g[i][j] = 1;
                else g[i][j] = 0;
            }
        }
        cin >> sx >> sy >> ex >> ey;
        sx++,sy++,ex++,ey++;
        if (g[sx][sy] || g[ex][ey]) {
            puts ("NO");
            continue;
        }
        if (dfs (sx,sy)) puts ("YES");
        else puts ("NO");
    }
    return 0;
}

思路2

$\text{BFS}$代码：

代码2

#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 110;
int K,n;
int sx,sy,ex,ey;
int g[N][N];
bool vis[N][N];
int dx[] = {0,-1,0,1},dy[] = {-1,0,1,0};
int main () {
    cin >> K;
    while (K--) {
        cin >> n;
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                char ch;
                cin >> ch;
                if (ch == '#') g[i][j] = 1;
                else g[i][j] = 0;
            }
        }
        cin >> sx >> sy >> ex >> ey;
        sx++,sy++,ex++,ey++;
        if (g[sx][sy] || g[ex][ey]) {
            puts ("NO");
            continue;
        }
        queue <PII> q;
        q.push ({sx,sy});
        bool ans = false;
        memset (vis,false,sizeof (vis));
        while (q.size ()) {
            PII t = q.front ();
            if (t.x == ex && t.y == ey) {
                ans = true;
                break;
            }
            q.pop ();
            for (int i = 0;i < 4;i++) {
                int a = t.x + dx[i],b = t.y + dy[i];
                if (a < 1 || a > n || b < 1 || b > n || g[a][b] || vis[a][b]) continue;
                vis[a][b] = true;
                q.push ({a,b});
            }
        }
        if (ans) puts ("YES");
        else puts ("NO");
    }
    return 0;
}