DFS 找路径算法。时间复杂度 $O(N^2)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 105;
char g[N][N];
int k, n;

// static constexpr int dirs[] { 0, -1, 0, 1, 0 }; // 一维方向数组 (上，左， 下，右)

bool hasPath(int x, int y, const int tx, const int ty) {

  if (x < 0 || y < 0 || x == n || y == n || g[y][x] == '#')
    return false;

  // reach to the goal!
  if (x == tx and y == ty) return true;

  g[y][x] = '#'; // mark as seen (标访为访问过)

  /* for (int i = 0; i < 4; ++i)
    if (hasPath(x + dirs[i], y + dirs[i + 1], tx, ty)) return true;

  return false; */

  return hasPath(x - 1, y, tx, ty)  // 左
      || hasPath(x + 1, y, tx, ty)  // 右
      || hasPath(x, y - 1, tx, ty)  // 上
      || hasPath(x, y + 1, tx, ty); // 下
}

int main() {
  cin >> k;
  while (k--) {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> g[i];

    int sx, sy, tx, ty;
    cin >> sy >> sx >> ty >> tx;

    if (g[sy][sx] == '#' || g[ty][tx] == '#') {
      puts("NO"); // 这是个坑! 如果起点或者终点有一个不能通行(为#)，则看成无法办到。
      continue;
    }

    puts(hasPath(sx, sy, tx, ty) ? "YES" : "NO");
  }

  return 0;
}