四連通檢測

印度阿三17 2019-02-21

展開全文

題目描述：

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

　　例如：

　　程序應該輸出：

false
true
true

思路：

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

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

　　還有就是當退回到當前狀態(tài)的時候需要進行回溯，因為我們在訪問之后有可能當前的節(jié)點走下去是不符合的，所以需要把之前訪問過的痕跡清除掉以便在下次嘗試其它路徑的時候能夠訪問到當前的節(jié)點。

代碼：

 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.左邊位置上的值要和現(xiàn)在的值相同
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 }

結果：