题意翻译

由于近期的降雨,雨水汇集在农民约翰的田地不同的地方。我们用一个 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

解题思路:

  1.  设置一个标记数组st[][],标记 w 网格访问过 
  2. 水的流向有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;
} 

希望能帮助到各位同志,祝天天开心,学业进步!

Logo

集算法之大成!助力oier实现梦想!

更多推荐