题目描述

小白和他的朋友周末相约去召唤师峡谷踏青。他们发现召唤师峡谷的地图是由一块一块格子组成的，有的格子上是草丛，有的是空地。草丛通过上下左右 4 个方向扩展其他草丛形成一片草地，任何一片草地中的格子都是草丛，并且所有格子之间都能通过上下左右连通。如果用’#‘代表草丛，’.'代表空地，下面的峡谷中有 2 片草地。

##…
…##

处在同一个草地的 2 个人可以相互看到，空地看不到草地里面的人。他们发现有一个朋友不见了，现在需要分头去找，每个人负责一片草地，想知道他们至少需要多少人。

输入

第一行输入 n, m (1 ≤ n,m ≤ 100) 表示峡谷大小。
接下来输入 n 行字符串表示峡谷的地形。

输出

输出至少需要多少人。

样例

输入

5 6
.#....
..#...
..#..#
...##.
.#....

输出

5

思路

1. 题意为求草丛数量
2. 采用dfs
3. 二维数组mp[][]保存地图
4. 如果当前位置是草丛或者没有被访问过就开始搜索四周
5. 搜四周的时候用递归保证四周都是#

#include <iostream>
using namespace std;
char mp[105][105];
int vis[105][105];
int m,n;
void dfs(int x,int y){if(x<0||x>=n||y<0||y>=n||vis[x][y]||mp[x][y]=='.'){return;}vis[x][y]=true;dfs(x+1,y);dfs(x-1,y);dfs(x,y+1);dfs(x,y-1);
}
int main(){int cnt=0;cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>mp[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(!vis[i][j]&&mp[i][j]=='#'){dfs(i,j);cnt++;}}}cout<<cnt<<endl;
}

另一种dfs格式

void dfs(int x,int y){int tx,ty;for(int i=0;i<4;i++){tx=x+dir[i][0];ty=y+dir[i][1];if(tx>=0&&tx<n&&ty>=0&&ty<m&&vis[tx][ty]==0&&s[tx][ty]=='#'){vis[tx][ty]=1;dfs(tx,ty);}}
}

统一代码风格
关于连通块儿问题dfs中要判断是否到边界或者不适合的地方

#include <iostream>
using namespace std;
int n,m,x,y,cnt;
char maze[100][100];
bool vis[100][100];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool in(int x,int y){return x>=0&&x<n&&y>=0&&y<m;
}
void dfs(int x,int y){if(x<0||x>=n||y<0||y>=n||vis[x][y]||maze[x][y]=='.'){return;}vis[x][y]=1;for(int i=0;i<4;i++){int tx=x+dir[i][0];int ty=y+dir[i][1];if(in(tx,ty)&&maze[tx][ty]=='#'&&!vis[tx][ty]){dfs(tx,ty);}}
}
int main(){cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>maze[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(!vis[i][j]&&maze[i][j]=='#'){dfs(i,j);cnt++;}}}cout<<cnt<<endl;return 0;
}