蓝桥杯 BFS 卫星扫描（中等）

问题描述

你正在用卫星绘制一个遥远的星球。 你的卫星捕捉到了行星表面的图像。拍摄的部分可以是 模拟成网格。每个网格单元要么是陆地，要么是水，要么被云覆盖。云意味着 表面可能是陆地，也可能是水，但我们不能说。 岛屿是一组相连的陆地细胞。如果两个单元共享一条边，则认为它们是连接的。 给定图像，确定与给定一致的最小岛数 信息。

输入 第一行输入包含两个空格分隔的整数n和m (1 ≤ n，m ≤ 50)。 接下来的n行每一行都包含m个字符，描述卫星图像。陆地细胞是 用“L”表示，水细胞用“W”表示，被云覆盖的细胞用“C”表示。

 输出 在一行上打印一个整数，表示一致的最小岛数 使用给定的网格。



输入

4 5

CCCCC

CCCCC

CCCCC

CCCCC



输出 0



输入

3 2

LW

CC

WL

输出 1

解题思路

只有把所有可能与陆地链接的C想象成陆地,才能实现陆地的最小数量.

循环所有陆地:

1.四周有L链接的C,陆地不断感染附近的C成为新陆地继续感染.

2.四周是水链接的C将它想象成水

3.四周是水链接的L,那没办法了,只能被计算是一个完整陆地

参考代码

import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static char[][] map = {{'L','W' },{'C','C'},{'W','L'}};
	static boolean[][] check = new boolean[map.length][map[0].length];
	static int count = 0;
	//坐标轴移动数组
	static int[] dx = { 1, -1, 0, 0};
	static int[] dy = { 0, 0, -1, 1};
	public static void main(String[] args) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if (map[i][j] == 'L' && !check[i][j]) {
					count++;
					check[i][j] = true;
					bfs(i,j);//进行bfs搜索讲与陆地链接的C连接起来
				}
			}
		}
		System.out.println(count);
	}
	
	private static void bfs(int i, int j) {
		// TODO Auto-generated method stub
		Queue<Integer> x = new LinkedList<Integer>();
		Queue<Integer> y = new LinkedList<Integer>();
		x.add(i);
		y.add(j);
		while (!x.isEmpty()) {
			//取出队列中的坐标
			int tx = x.poll();
			int ty = y.poll();
			//根据移动方向，生成新的坐标
			for (int k = 0; k < dx.length; k++) {
				int nx = tx + dx[k];
				int ny = ty + dy[k];
				if (nx >= 0 && ny >= 0 && nx < map.length && ny < map[0].length && map[nx][ny] != 'W' && !check[nx][ny]) {
					x.add(nx);
					y.add(ny);
					check[nx][ny] = true;//将新的坐标标记访问
				}
			}
		}
	}
}