欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Lake Counting

程序员文章站 2022-07-14 21:04:01
...

有一个大小为 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
深度优先搜索
从任意的W开始,不停地把邻接的部分用’.‘代替。1次DFS后与初始的这个W连接的所有W就都被替换成了’.’,因此直到图中不再存在W为止,

java实现

import java.util.Scanner;

public class Main {
	static char arr[][];
	static int sum,N,M;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn = new Scanner(System.in);
		sum=0;
		N=scn.nextInt();
		M=scn.nextInt();
		arr=new char[N][M];
		for(int i=0;i<N;i++) {
			arr[i]=scn.next().toCharArray();
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(arr[i][j]=='W') {
					f(i,j);
					sum++;
				}
			}
		}
		System.out.println(sum);
	}
	private static void f(int i, int j) {
		// TODO Auto-generated method stub
		for(int a=i-1;a<=i+1;a++) {
			for(int b=j-1;b<=j+1;b++) {
				if(a<0||b<0||a>=N||b>=M) continue;
				if(arr[a][b]=='W') {
					arr[a][b]='.';
					f(a,b);
				}
			}
		}
	}

}