题目大意
有一个大小为 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。
采用深度优先搜索,从任意的w开始,不断把邻接的部分用'.'代替,1次DFS后与初始这个w连接的所有w就全都被替换成'.'(为了防止回溯搜索导致死循环,把已经扫到的洼地的水抽干),因此直到图中不再存在W为止,总共进行DFS的次数就是答案。8个方向对应8个状态转移,每个格子作为DFS的参数最多调用一次,因时间复杂度为O(8nm)=O(nm)
。
其中的状态转移写法比较妙~
代码
package BlueCup.Seven_recursion;
import java.util.Scanner;
public class Dfs3水洼的数目 {
static int n,m;
public static void main(String[] args) {
Scanner cin =new Scanner(System.in);
n=cin.nextInt();
m=cin.nextInt();
char [][] a=new char[n][];
int cnt=0;
for (int i = 0; i < n; i++) {
a[i]=cin.next().toCharArray();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(a[i][j]=='W') {
dfs(a, i, j);//清除一个水洼
cnt++;//计数
}
}
}
System.out.println(cnt);
}
private static void dfs(char[][] a, int i, int j) {
a[i][j]='.';
for (int k = -1; k <2 ; k++) {//-1 0 1 9种状态
for (int l = -1; l <2 ; l++) {
if(k==0&&l==0){ //不动的状态去除
continue;
}
if(i+k>=0&&i+k<=n-1&&j+l>=0&&j+l<=m-1){//边界检测 行 列 八个平行状态
if(a[i+k][j+l]=='W'){
dfs(a,i+k,j+l);
}
}
}
}
}
}
本文作者:Author: 寒光博客
文章标题:[挑战程序设计]水洼数目 dfs
本文地址:https://dxoca.cn/Algorithm/222.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/222.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
妙啊 妙~
可以