P1596 [USACO10OCT] Lake Counting S(DFS)
一个网格与其周围的八个网格相连,而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图,确定当中有多少水坑。由于近期的降雨,雨水汇集在农民约翰的田地不同的地方。我们用一个 N×M(1≤N≤100,1≤M≤100) 的网格图表示。第 2 行到第 N+1 行:每行 M 个字符,每个字符是。输入第 1 行:两个空格隔开的整数:N 和 M。,它们表示网格图中的一排。希望
·
题意翻译
由于近期的降雨,雨水汇集在农民约翰的田地不同的地方。我们用一个 N×M(1≤N≤100,1≤M≤100) 的网格图表示。每个网格中有水(W
) 或是旱地(.
)。一个网格与其周围的八个网格相连,而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图,确定当中有多少水坑。
输入第 1 行:两个空格隔开的整数:N 和 M。
第 2 行到第 N+1 行:每行 M 个字符,每个字符是 W
或 .
,它们表示网格图中的一排。字符之间没有空格。
输出一行,表示水坑的数量。
输入输出样例
输入 #1复制
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.
输出 #1复制
3
题目链接:https://www.luogu.com.cn/problem/P1596
学习链接:DFS正确入门方式 | DFS + 递归与递推习题课(上) | 一节课教你爆搜!_哔哩哔哩_bilibili
解题思路:
- 设置一个标记数组st[][],标记 w 网格访问过
- 水的流向有8个方向
代码如下:
#include<bits/stdc++.h>
using namespace std;
int n,m;//n行m列
char ch[105][105];//田地矩阵
int st[105][105];//标记数组
int x[8]={-1,-1,0,1,1,1,0,-1};//x轴的偏移量
int y[8]={0,1,1,1,0,-1,-1,-1};//y轴的偏移量
int cnt=0;//累计水坑数量
void dfs(int x1,int y1)
{
for(int i=0;i<8;i++)
{
//下一个流向的网格坐标
int nx=x1+x[i];
int ny=y1+y[i];
//若网格越界,跳过
if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
//若网格是水且未被标记过
if(ch[nx][ny]=='W' && st[nx][ny]==0)
{
st[nx][ny]=cnt;
//枚举下一个网格
dfs(nx,ny);
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>ch[i];//输入一行字符串
//初始化st数组
memset(st,0,sizeof(st));
//遍历未标记的 w 网格
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
//若该网格是 w 网格,且未被标记过,搜索与它同一个水坑的网格
if(ch[i][j]=='W' && st[i][j]==0)
{
cnt++;//累计水坑数量
st[i][j]=1;//标记水坑第一个网格访问过
dfs(i,j);//从(i,j)开始搜索与它同一个水坑的网格
}
}
}
cout<<cnt<<endl;
return 0;
}
希望能帮助到各位同志,祝天天开心,学业进步!
更多推荐
所有评论(0)