四连通检测

题目描述：

　　给定一个方阵，定义连通：上下左右相邻，并且值相同。可以想象成一张地图，不同的区域被涂以不同颜色。
　　输入：
　　整数N, (N<50)表示矩阵的行列数
　　接下来N行，每行N个字符，代表方阵中的元素
　　接下来一个整数M，(M<1000)表示询问数
　　接下来M行，每行代表一个询问，
　　格式为4个整数，y1,x1,y2,x2，
　　表示询问(第y1行,第x1列) 与 (第y2行,第x2列) 是否连通。
　　连通输出true，否则false

　　例如：

　　程序应该输出：

false
true
true

思路：

　　这道题目应该使用DFS来解决，这里区分一下图的DFS和BFS。图的DFS还是和树的DFS一样，一条路走到黑，而图的BFS则是遍历当前节点的每一个邻居，遍历完成后遍历下一个节点的所有邻居。

　　所以这道题目最好采用DFS来解决。图与树不一样，它在递归的过程中搜索到下一层的时候会回到上一层又进行相同的递归那么这样就会在递归中一直出不去造成死循环，所以在这里进行深搜需要加上当前节点是否被访问的标志当进入下一次的递归的时候如果上一次的节点被标记过那么就不会再回来进行相同的递归了。

　　还有就是当退回到当前状态的时候需要进行回溯，因为我们在访问之后有可能当前的节点走下去是不符合的，所以需要把之前访问过的痕迹清除掉以便在下次尝试其它路径的时候能够访问到当前的节点。

代码：

 1 import java.util.Scanner;
 2 
 3 public class 图的dfs_连通检测 {
 4     public static void main(String[] args) {
 5         Scanner scanner = new Scanner(System.in);
 6         int N = scanner.nextInt();
 7         scanner.nextLine();
 8         char[][] graph = new char[N][N];
 9         for (int i = 0; i < N; i++) {
10             graph[i] = scanner.nextLine().toCharArray();
11         }
12         int M = scanner.nextInt();
13         int[][] query = new int[M][4];
14         for (int i = 0; i < M; i++) {
15             for (int j = 0; j < 4; j++) {
16                 query[i][j] = scanner.nextInt();
17             }
18         }
19         // M个起点和终点
20         for (int i = 0; i < M; i++) {
21             // 对每个起点和终点，检查是否连通
22             boolean ok = check(graph, new int[N][N], query[i]);
23             System.out.println(ok);
24         }
25     }
26 
27     /**
28      * 检查两个坐标点在这个图中是否连通
29      * 
30      * @param graph 原始图
31      * @param label 标记
32      * @param points 起点和终点的坐标 x1 y1 x2 y2
33      * @return
34      */
35     private static boolean check(char[][] graph, int[][] label, int[] points) {
36         int x1 = points[0];
37         int y1 = points[1];
38         int x2 = points[2];
39         int y2 = points[3];
40         // 起点和终点重合了，就可以返回true
41         if (x1 == x2 && y1 == y2) {
42             return true;
43         }
44 
45         int value = graph[x1][y1];
46         boolean f1 = false;
47         boolean f2 = false;
48         boolean f3 = false;
49         boolean f4 = false;
50         // 往左走，1.不能走出去，2.左边的位置没有被访问过，3.左边位置上的值要和现在的值相同
51         if (x1 - 1 >= 0 && label[x1 - 1][y1] == 0 && graph[x1 - 1][y1] == value) {
52             label[x1 - 1][y1] = 1; // 坐标的位置标记为已访问
53             points[0] = x1 - 1; // 把左边的点作为新起点，递归
54             f1 = check(graph, label, points);
55             // 回溯
56             label[x1 - 1][y1] = 0;
57             points[0] = x1;
58         }
59         // 往右走
60         if (x1 + 1 < graph.length && label[x1 + 1][y1] == 0 && graph[x1 + 1][y1] == value) {
61             label[x1 + 1][y1] = 1;
62             points[0] = x1 + 1;
63             f2 = check(graph, label, points);
64             label[x1 + 1][y1] = 0;
65             points[0] = x1;
66         }
67         // 往上走
68         if (y1 - 1 >= 0 && label[x1][y1 - 1] == 0 && graph[x1][y1 - 1] == value) {
69             label[x1][y1 - 1] = 1;
70             points[1] = y1 - 1;
71             f3 = check(graph, label, points);
72             label[x1][y1 - 1] = 0;
73             points[1] = y1;
74         }
75         // 往下走
76         if (y1 + 1 < graph.length && label[x1][y1 + 1] == 0 && graph[x1][y1 + 1] == value) {
77             label[x1][y1 + 1] = 1;
78             points[1] = y1 + 1;
79             f4 = check(graph, label, points);
80             label[x1][y1 + 1] = 0;
81             points[1] = y1;
82         }
83         return f1 || f2 || f3 || f4;
84     }
85 }

结果：