题解 | 迷宫

import java.util.Scanner;

public class Main {
    static int[][]move={{0,1},{0,-1},{1,0},{-1,0}};
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[]group=new int[n*m];
        int start=-1,end=-1;
        char[][]cs=new char[n][m];
        for (int i = 0; i < n; i++) {
            cs[i]=sc.next().toCharArray();
            for (int j = 0; j < m; j++) {
                group[i*m+j]=i*m+j;
                if(cs[i][j]=='S'){
                    start=i*m+j;
                }
                if(cs[i][j]=='E'){
                    end=i*m+j;
                }
            }
        }
        sc.close();
        //连通块处理
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(cs[i][j]!='#'){
                    for (int[] d : move) {
                        int x=i+d[0],y=j+d[1];
                        if(x>=0&&y>=0&&x<n&&y<m&&cs[x][y]!='#'){
                            union(i*m+j, x*m+y, group);
                        }
                    }
                }
            }
        }
        if(find(start, group)==find(end, group)){
            System.out.println("YES");
            //能直接走到，不需要使用激光
        }else{
            boolean[]row=new boolean[n];
            boolean[]col=new boolean[m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    for (int[] d : move) {
                        int x=i+d[0];
                        int y=j+d[1];//跟end一个连通块相邻的位置标记true，
                        if(x>=0&&y>=0&&x<n&&y<m&&find(x*m+y, group)==find(end, group)){
                            row[i]=col[j]=true;
                        }
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {//如果start一个连通块，同时该行或者列标记true
                    //说明可以用激光到达
                    if(find(i*m+j, group)==find(start, group)&&(row[i]||col[j])){
                        System.out.println("YES");
                        return;
                    }
                }
            }
            System.out.println("NO");
        }

    }
    static void union(int x, int y,int[]group){
        int px=find(x, group);
        int py=find(y, group);
        if(px>py){
            group[px]=py;
        }else if(px<py){
            group[py]=px;
        }
    }
    static int find(int x,int[]group){
        if(group[x]==x){
            return x;
        }
        return group[x]=find(group[x], group);
    }
}