八连通块
2023-03-14 09:44:39 时间
题目描述：
输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。 如果两个字符“@”所在的格子相邻（横、竖或者对角线方向），就说它们属于同一个八连块。
思路：
还是使用图的DFS来解决问题，需要注意的都在代码注释里面。
代码：
1 public class 图的dfs_FloodFill { 2 private static char[][] data = { 3 "*@@*@".toCharArray(), 4 "**@*@".toCharArray(), 5 "****@".toCharArray(), 6 "@@@*@".toCharArray(), 7 "@@**@".toCharArray(), 8 }; 9 // 记录区块数 10 private static int cnt; 11 // 访问记录 12 // private static int[][] vis = new int[data.length][data[0].length]; 13 14 private static void dfs(int r, int c) { 15 // 设计出口 16 // 超出边界了 17 if (r < 0 || r >= data.length || c < 0 || c >= data[0].length) 18 return; 19 // 不是@ 20 if (data[r][c] == '*') 21 return; 22 // 已经扫描过了，这是深度搜索必须考虑到的点 23 // if (vis[r][c] == 1) return; 24 25 // 标记为已访问 26 // vis[r][c] = 1; 27 data[r][c] = '*'; 28 // 八个方向去探测，继续搜索 29 dfs(r + 1, c); 30 dfs(r - 1, c); 31 dfs(r, c + 1); 32 dfs(r, c - 1); 33 dfs(r + 1, c + 1); 34 dfs(r + 1, c - 1); 35 dfs(r - 1, c - 1); 36 dfs(r - 1, c + 1); 37 } 38 39 public static void main(String[] args) { 40 // 遍历每个字符 41 for (int i = 0; i < data.length; i++) { 42 for (int j = 0; j < data[0].length; j++) { 43 // if (vis[i][j] == 0 && data[i][j] == '@') 44 // 找到@就开始深搜，深搜的过程就是把@变为*的过程 45 if (data[i][j] == '@') { 46 dfs(i, j); 47 // 当深搜完成，说明当前字符所在的八连块全部被修改为*，应该块的计数+1，并寻找下一个@ 48 // 这种方法很巧妙 就可以标记已经访问过 49 ++cnt; 50 } 51 } 52 } 53 System.out.println(cnt); // 输出3 54 } 55 }