【DFS】求水洼的数目
2023-03-14 09:45:08 时间
题目:
有一个大小为 N*M 的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼?(八连通指的是下图中相对 W 的*的部分)
*** *W* ***
限制条件:N, M ≤ 100
样例输入:
N=10, M=12
园子如下图('W'表示积水, '.'表示没有积水)
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出:
3
思路:
这道题目很经典,值得以后多去研究研究。问题是要我们求解出连着的一片的水洼的数量,对于这类经典的问题,使用其它迭代等的方法是难以求解的,因为我们不知道连着的积水的区域有多少,对于这类问题的求解,我们是采用常用的无死角搜索的深度优先搜索dfs算法来解决,因为dfs能够帮助我们搜索出所有的可能,尝试去走每一条路线,直到所有的路线都被走完了,那么dfs就终止了。
其中涉及到搜索以自己为中心的八个方向的搜索,所以存在着八个平行状态的搜索,这里使用到了一个技巧就是使用两层的for循环来进行处理。
这里还有一个技巧就是当发现这个位置有积水的时候就把这个位置变为干燥,这样在往下搜索的过程中就能避免往上搜索而造成递归无法出去的问题。这样当一个dfs搜索完之后那么它周围的积水都被清除掉了,那么继续寻找下一个有积水的地方然后进行dfs,当所有的积水区域都被干燥之后那么水洼的数量就计算出来了。
代码:
1 import java.util.Scanner; 2 3 public class 水洼数 { 4 5 private static int n; 6 private static int m; 7 8 public static void main(String[] args) { 9 Scanner sc = new Scanner(System.in); 10 n = sc.nextInt(); 11 m = sc.nextInt(); 12 char[][] a = new char[n][]; 13 for (int i = 0; i < n; i++) { 14 a[i] = sc.next().toCharArray(); 15 } 16 int cnt = 0; 17 for (int i = 0; i < n; i++) { 18 for (int j = 0; j < m; j++) { 19 if (a[i][j] == 'W') { 20 dfs(a, i, j);// 清除一个水洼 21 cnt++; 22 } 23 } 24 } 25 System.out.println(cnt); 26 } 27 28 private static void dfs(char[][] a, int i, int j) { 29 a[i][j] = '.'; 30 31 for (int k = -1; k < 2; k++) {// -1,0,1 32 for (int l = -1; l < 2; l++) {// -1,0,1 33 if (k == 0 && l == 0) 34 continue; 35 36 if (i + k >= 0 && i + k <= n - 1 && j + l >= 0 && j + l <= m - 1) { 37 if (a[i + k][j + l] == 'W') 38 dfs(a, i + k, j + l); 39 } 40 } 41 } 42 } 43 44 }
结果:
相关文章
- Linux跟踪技术之Ebpf
- 数据孤岛是否正在破坏数字化转型?
- Linux 中的负载高低和 CPU 开销并不完全对应
- 如何优雅的消除系统重复代码
- 英伟达显卡驱动程序 525.78.01 发布:Linux 等平台更好支持 Vulkan X11 应用
- “实时数仓”若干问?
- 效力 6 年后,Linux Kernel 4.9 LTS 已终止支持
- Budgie 10.7 即将带来三项关键改进
- 线上一次JVM FullGC搞得整晚都没睡,彻底崩溃
- VS Code 这么牛,再次印证了一句名言
- 如何在 Linux 中使用 的 mv 命令九个有用例子
- 如何使用 Bash 连接字符串
- Cloudera:定位混合数据公司,满足现代数据架构需求
- 编译器、虚拟机、操作系统,到底哪个更难?
- Nitrux 2.6.0 大胆抛弃 apt
- 不想Go 错误处理太臃肿,可以参考这个代码设计
- Kyligence Zen:助力企业实现智能指标驱动的管理与决策
- 你说的下游是 Upstream 吧?
- Fedora 38 将发布 Budgie 和 Sway 官方定制版
- 用位运算为你的程序加速