超时做法

我自己的做法是做两遍BFS，因为受到了统计岛屿个数的启发，想要多次做BFS，结果我做了（1 + 墙数）这么多次BFS，最后超时了。具体做法是先从起点做一遍BFS，然后找到所有的陆地，将从路拓展出去的墙的坐标收集起来，相当于是把第一层墙记录下来了，因为题目我们可以打破一堵墙。

然后再每块墙做起点，分别正常做BFS，遇到墙就停下来，因为我们只能打破一堵墙，看是不是能够到达终点！当然如果第一次做BFS就可以连通的话，也用不着做第二次BFS了。

结果：测试数据： 8/10

正解-染色法-直接贴图

妙不可言

（1）染色法的核心就是墙的两边染不同的颜色，我们最多只能打破一个墙，所以在遍历的时候只需要遍历这个墙的上、下、左、右是不是有不同的颜色存在即可。

（2）我们在判断是不是墙的四周有无颜色也是有技巧性的，其实我们可以设置两个flag遍历， 如果一边出现了颜色1，flag1 = true，另一边如果有0的话，flag2 = true，但是这里用了更加巧妙的方法就是位运算，它把颜色1的值设置为1，将颜色2的值设置为2，然后没有颜色的地方默认为0，那么墙是没有颜色的，这里用到了或运算的性质，1 = 01，2 = 10，0 = 00，这三种数，无论怎么或运算，只有1和2或在了一起，才能得到3 = 11，因此我们将墙的四周或起来，墙并不会影响我们的结果，重复颜色或起来也没关系，但是如果我们得到了3，那么就代表这块墙的左右两边是存在不同的颜色，那么是可通的！！！

（3）这样我们只需要做2遍DFS，然后枚举所有墙的4个方向即可

CODE

import java.util.Scanner;

public class Main{
    static int N = 1010;
    static int [] dx = new int [] {-1, 0, 0, 1};
    static int [] dy = new int [] {0, 1, -1, 0};
    static int n, m;
    static int sx, sy, ex, ey;
    static char [][] g = new char [N][N];
    static int [][] color = new int [N][N];

    static void dfs(int x, int y, int c) {
        color[x][y] = c;
        for(int i = 0; i < 4; i ++){
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(g[a][b] == '#') continue; //染路
            if(color[a][b] != 0) continue; //染过了，就不染色了
            dfs(a, b, c); //证明这个格子可以被染色
        }
    }

    static boolean check(int x, int y) {
        int u = 0;
        for(int i = 0; i < 4; i ++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            u |= color[a][b];
        }

        return u == 3;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        sx = sc.nextInt() - 1;
        sy = sc.nextInt() - 1;
        ex = sc.nextInt() - 1;
        ey = sc.nextInt() - 1;

        for(int i = 0; i < n; i ++) {
            g[i] = sc.next().toCharArray();
        }

        dfs(sx, sy, 1); 

        if(color[ex][ey] == 1) {
            System.out.println("Yes");
            return;
        }

        dfs(ex, ey, 2);

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
            {
                if(g[i][j] == '#' && check(i, j)) {
                    System.out.println("Yes");
                    return;
                }
            }

        System.out.println("No");

    }
}