HDU 2952 Counting Sheep 深搜

本文主要是介绍HDU 2952 Counting Sheep 深搜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给一个h*w的图，求有多少个#块，如果上下左右任意一个连着就被视为一块，有传递性。

想法：标记，深搜。

#include<iostream>
#include<cstring>
using namespace std;
int h,w;
char map[120][120];
bool mark[120][120];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
void dfs(int x,int y)
{for(int i=0;i<4;i++){int nx=x+dir[i][0];int ny=y+dir[i][1];if(nx<0||nx>=h||ny<0||ny>w) continue;if(mark[nx][ny]) continue;if(map[nx][ny]!='#') continue;mark[nx][ny]=true;dfs(nx,ny);}return;
}
int main()
{int t;cin>>t;while(t--){cin>>h>>w;for(int i=0;i<h;i++)cin>>map[i];memset(mark,false,sizeof(mark));int sum=0;for(int i=0;i<h;i++){for(int j=0;j<w;j++){if(map[i][j]=='#'&&!mark[i][j]){dfs(i,j);sum++;}}}cout<<sum<<endl;}return 0;
}

这篇关于HDU 2952 Counting Sheep 深搜的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---