Lake Counting(DFS连通图)
2024-08-25 08:47:02
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.
题目意思:查找所有由w组成的区域,八面搜索,只要周围有w就能连接在一起组成一个区域。
解题思路:这是一道很基本的深搜例题,当成模板直接来使用吧。
上代码:
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
char map[][];
int vis[][];///标记数组
int dir[][]={{,},{-,},{,},{,-},{,},{-,-},{,-},{-,}};
int n,m;
void DFS(int x,int y)
{
int a,b,i;
vis[x][y]=;
for(i=;i<;i++)
{
a=x+dir[i][];
b=y+dir[i][];
if(a>=&&a<n&&b>=&&b<m&&vis[a][b]==&&map[a][b]=='W')
{
DFS(a,b);
}
}
return ;
}
int main()
{
int count,i,j;
memset(map,,sizeof(map));
memset(vis,,sizeof(vis));
scanf("%d%d",&n,&m);
getchar();
count=;
for(i=;i<n;i++)
{
scanf("%s",map[i]);
}
for(i=;i<n;i++)
{
for(j=;j<m;j++)
{
if(vis[i][j]==&&map[i][j]=='W')
{
count++;
DFS(i,j);
}
}
}
printf("%d\n",count);
return ;
}
最新文章
- 文件IO函数和标准IO库的区别
- 【总结】matlab求两个序列的相关性
- chrome升级54以后,显示Adobe Flash Player 因过期而遭到阻止
- PL/0编译器(java version)&ndash;Pcode.java
- 让html元素随浏览器的大小自适应垂直居中
- poj3263 Tallest Cow
- poj 3041 Asteroids (二分图的最大匹配 第一题)
- jqery筛选
- C# Winform 实现自定义半透明loading加载遮罩层
- android 中对apache httpclient及httpurlconnection的选择
- 单片机:STC89C52的最小单元
- 15 Action View 以及监听 的使用
- 使用100%面向过程的思维方式来写java程序
- Python11/23--mysql用户管理/pymysql
- redis安装,修改配置文件,多实例部署 redis-server
- 命令行启用IIS Express
- DDD Quickly - 读书笔记
- 28 - 生成器交互-__slots__-未实现异常
- UVALive 6907 Body Building
- Web应用程序项目OxiteSite已配置为使用IIS.在本地计算机上找不到服务器