$$\color{Red}{迷宫【DFS之联通性模型】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

深度优先遍历————>改写走迷宫————>只能搜到连通性，无法做到最优解

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    static int N = 110, T, n, x1, y1, x2, y2;
    static char[][] g = new char[N][N];
    static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static boolean dfs(int x, int y) {
        if (g[x][y] == '#') return false;
        if (x == x2 && y == y2) return true;
        g[x][y] = '#';

        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 (g[a][b] == '#') continue;
            if(dfs(a, b)) return true;
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            n = Integer.parseInt(br.readLine());
            for (int i = 0; i < n; i++) {
                String s1 = br.readLine();
                for (int j = 0; j < n; j++) g[i][j] = s1.charAt(j);
            }
            String[] s2 = br.readLine().split(" ");
            x1 = Integer.parseInt(s2[0]);
            y1 = Integer.parseInt(s2[1]);
            x2 = Integer.parseInt(s2[2]);
            y2 = Integer.parseInt(s2[3]);
            if(dfs(x1, y1)) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}