題目描述：

　　給定一個(gè)方陣，定義連通：上下左右相鄰，并且值相同?？梢韵胂蟪梢粡埖貓D，不同的區(qū)域被涂以不同顏色。
　　輸入：
　　整數(shù)N, (N<50)表示矩陣的行列數(shù)
　　接下來N行，每行N個(gè)字符，代表方陣中的元素
　　接下來一個(gè)整數(shù)M，(M<1000)表示詢問數(shù)
　　接下來M行，每行代表一個(gè)詢問，
　　格式為4個(gè)整數(shù)，y1,x1,y2,x2，
　　表示詢問(第y1行,第x1列) 與 (第y2行,第x2列) 是否連通。
　　連通輸出true，否則false

　　例如：

10
0010000000
0011100000
0000111110
0001100010
1111010010
0000010010
0000010011
0111111000
0000010000
0000000000
3
0 0 9 9
0 2 6 8
4 4 4 6

　　程序應(yīng)該輸出：

false
true
true

思路：

　　這道題目應(yīng)該使用DFS來解決，這里區(qū)分一下圖的DFS和BFS。圖的DFS還是和樹的DFS一樣，一條路走到黑，而圖的BFS則是遍歷當(dāng)前節(jié)點(diǎn)的每一個(gè)鄰居，遍歷完成后遍歷下一個(gè)節(jié)點(diǎn)的所有鄰居。

　　所以這道題目最好采用DFS來解決。圖與樹不一樣，它在遞歸的過程中搜索到下一層的時(shí)候會(huì)回到上一層又進(jìn)行相同的遞歸那么這樣就會(huì)在遞歸中一直出不去造成死循環(huán)，所以在這里進(jìn)行深搜需要加上當(dāng)前節(jié)點(diǎn)是否被訪問的標(biāo)志當(dāng)進(jìn)入下一次的遞歸的時(shí)候如果上一次的節(jié)點(diǎn)被標(biāo)記過那么就不會(huì)再回來進(jìn)行相同的遞歸了。

　　還有就是當(dāng)退回到當(dāng)前狀態(tài)的時(shí)候需要進(jìn)行回溯，因?yàn)槲覀冊谠L問之后有可能當(dāng)前的節(jié)點(diǎn)走下去是不符合的，所以需要把之前訪問過的痕跡清除掉以便在下次嘗試其它路徑的時(shí)候能夠訪問到當(dāng)前的節(jié)點(diǎn)。

代碼：

 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個(gè)起點(diǎn)和終點(diǎn)
20         for (int i = 0; i < M; i  ) {
21             // 對每個(gè)起點(diǎn)和終點(diǎn)，檢查是否連通
22             boolean ok = check(graph, new int[N][N], query[i]);
23             System.out.println(ok);
24         }
25     }
26 
27     /**
28      * 檢查兩個(gè)坐標(biāo)點(diǎn)在這個(gè)圖中是否連通
29      * 
30      * @param graph 原始圖
31      * @param label 標(biāo)記
32      * @param points 起點(diǎn)和終點(diǎn)的坐標(biāo) 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         // 起點(diǎn)和終點(diǎn)重合了，就可以返回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.左邊位置上的值要和現(xiàn)在的值相同
51         if (x1 - 1 >= 0 && label[x1 - 1][y1] == 0 && graph[x1 - 1][y1] == value) {
52             label[x1 - 1][y1] = 1; // 坐標(biāo)的位置標(biāo)記為已訪問
53             points[0] = x1 - 1; // 把左邊的點(diǎn)作為新起點(diǎn)，遞歸
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 }

結(jié)果：

?