您现在的位置是:首页 > 正文

POJ2386 Lake Counting【DFS、BFS】

2024-02-01 03:35:26阅读 2

Description

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

Output

* Line 1: The number of ponds in Farmer John's field.

Sample Input

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

Sample Output

3

Hint

OUTPUT DETAILS:
There are three ponds: one in the upper left, one in the lower left,and one along the right side.

 解题思路

题目大意:N*M(100*100)的地图中,有‘.’和‘W’两种地图元素,问其中有多少个由‘W’构成的八连通块。

解题思路:这是一道比较基础的搜索题目,这道题采用DFS或BFS都可以,遍历地图中的所有点,如果遇到‘W’就开始使用DFS从其八个方向开始搜索,当遇到‘W’时就将该点改为‘.’并从该点继续搜寻,直到无法再找到‘W’为止。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };

int n, m;
char map[110][110];

void DFS(int x, int y)
{
	if (x < 1 || x > n || y < 1 || y > m)			//越界
		return;
	if (map[x][y] != 'W')								//不属于连通块内
		return;     
	map[x][y]='.';										//已访问,改为背景
	for (int i = 0; i < 8; i++)
		DFS(x + dx[i], y + dy[i]);					//八连通dfs

}

int main()
{
	int cnt = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> map[i][j];
	for(int i = 1;i<=n;i++)
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j] == 'W')
			{
				DFS(i, j);
				cnt++;
			}
		}
	cout << cnt << endl;
	return 0;
}

 

网站文章

  • 1.2.24 Fastjson反序列化TemplatesImpl和JdbcRowSetImpl利用链分析(非常详细)

    1.2.24 Fastjson反序列化TemplatesImpl和JdbcRowSetImpl利用链分析(非常详细)

    本文的关于Fastjson1.2.24版本TemplatesImpl利用链的分析非常详细,如果你不是很熟悉该利用链,这篇文章非常适合你去学习,有比较详细的代码讲解。但是由于本人不是专业学习java的,只能以自己的理解去理解代码。应该不会差太多。有不懂可以评论区留言。...............

    2024-02-01 03:35:19
  • vue-print-nb 组件打印网页

    vue-print-nb 组件打印网页

    一、安装组件npm install vue-print-nb --save二、引入组件import Print from "vue-print-nb";import Vue from "vue";Vu...

    2024-02-01 03:35:10
  • K8S安装及卸载dashboard

    K8S安装及卸载dashboard

    k8s v1.23 安装dashboard v2.5.1; 三种暴漏dashboard的方式; 设置使用http访问dashboard;

    2024-02-01 03:34:40
  • Linux安装Redis数据库,实现远程连接

    Linux安装Redis数据库,实现远程连接

    Redis作为一款高速缓存的key value键值对的数据库,在许许多多的场景中广泛使用,由于是把数据存储在内存中,所以读写效率极高。下面介绍如何在内网虚拟机的linux中搭建redis并通过cpolar内网穿透实现公网访问。

    2024-02-01 03:34:34
  • Linux C语言中access函数的用法

    Linux C语言中access()函数的使用方法。

    2024-02-01 03:34:27
  • 工作记录---静态库和动态库

    1.静态库就是直接将需要的代码连接进可执行程序; 动态库就是在需要调用其中的函数时,根据函数映射表找到该函数然后调入堆栈执行。

    2024-02-01 03:33:57
  • 有名管道与无名管道以及他们之间的区别

    有名管道与无名管道以及他们之间的区别

    有名管道与无名管道以及他们之间的区别

    2024-02-01 03:33:51
  • 特征工程之mushroom classification

    库import numpy as np # linear algebraimport pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)import matplotlib.pyplot as pltimport seaborn as snsfrom matplotlib.pyplot import figure...

    2024-02-01 03:33:44
  • 简单区分数据库之中的1NF、2NF、3NF、BCNF

    简单理解主属性、非主属性、部分函数依赖、完全函数依赖、传递函数依赖。简单区分1NF、2NF、3NF、4NF

    2024-02-01 03:33:40
  • 【ensp的OSPF多区域配置】

    【ensp的OSPF多区域配置】

    ensp是华为公司提供的一款模拟器,它可以在计算机上模拟出真实的华为网络设备,并支持OSPF协议的配置。OSPF(Open Shortest Path First)是一种开放式最短路径优先协议,它可以...

    2024-02-01 03:33:09