题目描述
贝茜正计划着这一天如何美美地咀嚼春天的绿草，远望着农民约翰钟爱的并被分
割为R (1 <= R <= 100) 行和 C (1 <= C <= 100) 列的草场。她想去数一数草场
有多少个草丛。
每个草丛在地图上用’#‘来表示，或者两个’#'连在一起(但不是在一个对角线)，
给出草场地图，请告诉贝茜草场上一共有多少个草丛。
例如，下面有一张草场地图 R=5, C=6:
.#…
…#…
…#…#
…##.
.#…
这个草场一共有5个草丛。(1,2);
(2,3)+(3+3);
(3,6);
(4,4)+(4,5);
(5,2)
输入描述
第 1 行: 2个用空格隔开的整数 R , C
第 2 至 R+1 行: 草场地图信息
输出描述
草场上草丛的总个数。
【dfs|codevs【1569】最佳绿草】样例输入
5 6
.#…
…#…
…#…#
…##.
.#…
样例输出
5
#include
#include
using namespace std;
#define N 100 + 10
int dir[][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int n,m;
char a[N][N];
int ans;
bool isValid(int x,int y)
{
return (x >= 0 && x < n) && (y >= 0 && y < m) && (a[x][y] == '#');
}
int dfs(int x,int y)
{
if(isValid(x,y)) {
a[x][y] = '.';
for(int i = 0;
i < 4;
i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
dfs(nx,ny);
}
return 1;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 0;
i < n;
i++)
for(int j = 0;
j < m;
j++)
cin >> a[i][j];
for(int i = 0;
i < n;
i++)
for(int j = 0;
j < m;
j++)
ans += dfs(i,j);
//从左到右，从上到下找草地，并在该草地上深搜相连的草地
printf("%d\n",ans);
return 0;
}
推荐阅读
- 遇见蓝桥遇见你|小唐开始刷蓝桥（一）2020年第十一届C/C++ B组第二场蓝桥杯省赛真题
- DFS|使用DFS（深搜）遍历所有的序列所有的子组合（子序列）（排列组合中的组合）
- Pavel loves grid mazes（CodeForce 377A）
- DFS|CodeForces - 275B （广搜）
- 搜索|Wannafly模拟赛3-B 贝伦卡斯泰露（DFS）
- leetcode做题笔记|leetcode:Subsets
- CodeForces 377A
- DFS|CodeForces - 1099D（树上贪心+DFS）
- Codeforces Round #336 (Div. 1) D. Power Tree
- BFS|Solve The Maze（codeforces）