搜索:Flood Fill
Resolmi Newbie

1097. 池塘计数

农夫约翰有一片的矩形土地。最近,由于降雨的原因,部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内,如果包含雨水,则用”W”表示,如果不含雨水,则用”.”表示。

现在,约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘,即矩阵中共有多少片相连的”W”块。

输入格式

第一行包含两个整数

接下来行,每行包含个字符,字符为”W”或”.”,用以表示矩形土地的积水状况,字符之间没有空格。

输出格式

输出一个整数,表示池塘数目。

数据范围

输入样例:

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出样例:

3

解法一

经典 Flood Fill,搜索或者并查集都可,没啥好说的

import java.io.*;
import java.util.*;
class Main {

static int N;
static int M;
static boolean[][] vis;
static char[][] board;
static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, -1}, {-1, 1}, {-1, -1}, {1, 1}};

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
board = new char[N][M];
vis = new boolean[N][M];
for (int i = 0; i < N; i++) {
board[i] = sc.next().toCharArray();
}
int res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (!vis[i][j] && board[i][j] == 'W') {
res++;
dfs(i, j);
}
}
}
System.out.println(res);
}

public static void dfs (int x, int y) {
vis[x][y] = true;
for (int i = 0; i < dir.length; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
continue;
}
if (!vis[nx][ny] && board[nx][ny] == 'W') {
dfs(nx, ny);
}
}
}
}

1098. 城堡问题

   1   2   3   4   5   6   7  
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
(图 1)
# = Wall
| = No wall
- = No wall

方向:上北下南左西右东。
图 1 是一个城堡的地形图。

请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。

城堡被分割成 m∗n 个方格区域,每个方格区域可以有 0~4 面墙。

注意:墙体厚度忽略不计。

输入格式

第一行包含两个整数 m 和 n,分别表示城堡南北方向的长度和东西方向的长度。

接下来 m 行,每行包含 n 个整数,每个整数都表示平面图对应位置的方块的墙的特征。

每个方块中墙的特征由数字 P 来描述,我们用 1 表示西墙,2 表示北墙,4 表示东墙,8 表示南墙,P 为该方块包含墙的数字之和。

例如,如果一个方块的 P 为 3,则 3 = 1 + 2,该方块包含西墙和北墙。

城堡的内墙被计算两次,方块 (1,1) 的南墙同时也是方块 (2,1) 的北墙。

输入的数据保证城堡至少有两个房间。

输出格式

共两行,第一行输出房间总数,第二行输出最大房间的面积(方块数)。

数据范围

输入样例:

4 7 
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

输出样例:

5
9

解法一

题目很简单,但是怎么处理墙有点麻烦,我直接采用了最蠢的办法

import java.io.*;
import java.util.*;

public class AcWing1098_城堡问题 {
public static void main(String[] args) throws Exception {
new Main().main();
}
}

class Main {
// 2(3)
//1(2) 4(1)
// 8(0)

//下,右,左,上
static int[][] dir = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
static int n, m;
static boolean[][] wall;
static boolean[][] vis;
static int[][] board;

public static void main(String... args) throws Exception {
Scanner sc = new Scanner(new File("./input.txt"));
// Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
vis = new boolean[n][m];
wall = new boolean[16][4];
wall[2][3] = wall[1][2] = wall[4][1] = wall[8][0] = true;
wall[3][2] = wall[3][3] = true;
wall[5][1] = wall[5][2] = true;
wall[9][0] = wall[9][2] = true;
wall[6][1] = wall[6][3] = true;
wall[10][0] = wall[10][3] = true;
wall[12][0] = wall[12][1] = true;
wall[7][1] = wall[7][2] = wall[7][3] = true;
wall[11][0] = wall[11][2] = wall[11][3] = true;
wall[14][0] = wall[14][1] = wall[14][3] = true;
wall[13][0] = wall[13][1] = wall[13][2] = true;
wall[15][0] = wall[15][1] = wall[15][2] = wall[15][3] = true;
board = new int[n][m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++) {
board[i][j] = sc.nextInt();
}
}
int count = 0, max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!vis[i][j]) {
count++;
max = Math.max(max, dfs(i, j));
}
}
}
System.out.println(count);
System.out.println(max);
}

public static int dfs (int x, int y) {
vis[x][y] = true;
int area = 1;
for (int i = 0; i < dir.length; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || wall[board[x][y]][i]) {
continue;
}
if (!vis[nx][ny]) {
area += dfs(nx, ny);
}
}
return area;
}
}

解法二

优雅的位运算,东南西北对应的墙 1,2,4,8 就是,所以我们可以根据二进制的对应位的 0,1 状态判断该方向有没有墙

class Main {
// 2(0010)
//1(0001) 4(0100)
// 8(1000)
//左,上,右,下
static int[][] dir = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
static int n, m;
static boolean[][] vis;
static int[][] board;

public static void main(String... args) throws Exception {
Scanner sc = new Scanner(new File("./input.txt"));
// Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
vis = new boolean[n][m];
board = new int[n][m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++) {
board[i][j] = sc.nextInt();
}
}
int count = 0, max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!vis[i][j]) {
count++;
max = Math.max(max, dfs(i, j));
}
}
}
System.out.println(count);
System.out.println(max);
}

public static int dfs (int x, int y) {
vis[x][y] = true;
int area = 1;
for (int i = 0; i < dir.length; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
if (!vis[nx][ny] && ((board[x][y]>>i)&1) == 0) {
area += dfs(nx, ny);
}
}
return area;
}
}

1106. 山峰和山谷

FGD 小朋友特别喜欢爬山,在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排,他想知道山峰和山谷的数量。

给定一个地图,为 FGD 想要旅行的区域,地图被分为 n×n 的网格,每个格子 (i,j) 的高度 w(i,j) 是给定的。

若两个格子有公共顶点,那么它们就是相邻的格子,如与 (i,j) 相邻的格子有 (i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)。

我们定义一个格子的集合 S 为山峰(山谷)当且仅当:

  • S 的所有格子都有相同的高度。
  • S 的所有格子都连通。
  • 对于 s 属于 S,与 s 相邻的 s′ 不属于 S,都有 ws>ws′(山峰),或者 ws<ws′(山谷)。
  • 如果周围不存在相邻区域,则同时将其视为山峰和山谷。

你的任务是,对于给定的地图,求出山峰和山谷的数量,如果所有格子都有相同的高度,那么整个地图即是山峰,又是山谷。

输入格式

第一行包含一个正整数 n,表示地图的大小。

接下来一个 n×n 的矩阵,表示地图上每个格子的高度 w。

输出格式

共一行,包含两个整数,表示山峰和山谷的数量。

数据范围

输入样例 1:

5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8

输出样例 1:

2 1

输入样例 2:

5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7

输出样例 2:

3 3

解法一

一开始没看视频,自己写了个 DFS,然后死活过不去,卡在了第 17/20 个 case,改了好久也没改好,然后改成 BFS 一发就过了,BFS 连接每个点的连通块,然后比较每个块和四周不联通的块的高度大小,进而判断该连通块是山峰还是山谷

class Main {

static int n;
static boolean[][] vis;
static int[][] w;
static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, -1}, {-1, 1}, {-1, -1}, {1, 1}};
static Queue<Pair> queue = new LinkedList<>();
static class Pair {
int x, y;
public Pair (int x, int y) {
this.x = x;
this.y = y;
}
}
/*
*/
public static void main(String... args) throws Exception{
InputReader in = new InputReader(System.in);
// InputReader in = new InputReader(new FileInputStream("./input.txt"));
n = in.nextInt();
w = new int[n][n];
vis = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
w[i][j] = in.nextInt();
}
}
int up = 0, down = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!vis[i][j]) {
int temp = bfs(i, j);
if (temp == 1 || temp == 2) up++;
if (temp == -1 || temp == 2) down++;
}
}
}
System.out.println(up + " " + down);
}

//对这个点进行广搜,并且进行标记
//返回值:-1 山谷,0 啥也不是,1 山峰,2 既是山峰也是山谷
public static int bfs(int x, int y) {
queue.clear();
queue.add(new Pair(x, y));
vis[x][y] = true;
boolean up = false, down = false;
while (!queue.isEmpty()){
Pair p = queue.poll();
for (int i = 0; i < dir.length; i++) {
int nx = p.x + dir[i][0];
int ny = p.y + dir[i][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
continue;
}
if (w[p.x][p.y] < w[nx][ny]) {
down = true;
} else if (w[p.x][p.y] > w[nx][ny]) {
up = true;
} else if (!vis[nx][ny]) {
vis[nx][ny] = true;
queue.add(new Pair(nx, ny));
}
}
}
//up 和 down 同时满足,说明周围既有比当前大的,也有比当前小的
if (up && down) return 0;
if (up) return 1;
if (down) return -1;
//up 和 down 都不满足,所有元素一样,既是山峰也是山谷
return 2;
}
}
  • 本文标题:搜索:Flood Fill
  • 本文作者:Resolmi
  • 创建时间:2021-03-25 00:00:00
  • 本文链接:https://imlgw.top/2021/03/25/89c67f8e/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论