题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 105;

char maze[N][N];
bool st[N][N];
int n;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool dfs(int x, int y, int c, int d)
{
    if (maze[x][y] == '#') return false;//有障碍物就返回false；
    if (x == c && y == d) 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 || st[a][b]) continue;
        if (dfs(a, b, c, d)) return true;
    }

    return false;
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        memset(st, 0, sizeof st);
        cin >> n;
        for (int i = 0; i < n; i ++) cin >> maze[i];
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        if (dfs(a, b, c, d)) puts("YES");
        else puts("NO");
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla