數羊/牛/石油群類的，就是分堆的搜索。

這里考慮用深搜or廣搜，憑借題目給的地圖范圍，范圍大的用廣搜。

TOJ 2799 Counting Sheep

A while ago I had trouble sleeping. I used to lie awake, staring at the ceiling, for hours and hours. Then one day my grandmother suggested I tried counting sheep after I'd gone to bed. As always when my grandmother suggests things, I decided to try it out. The only PRoblem was, there were no sheep around to be counted when I went to bed.

輸入

The first line of input contains a single number T, the number of test cases to follow.Each test case begins with a line containing two numbers, H and W, the height and width of the sheep grid. Then follows H lines, each containing W characters (either # or .), describing that part of the grid.

輸出

For each test case, output a line containing a single number, the amount of sheep flock son that grid according to the rules stated in the problem description.Notes and Constraints0 < T <= 1000 < H,W <= 100

樣例輸入

24 4#.#..#.##.##.#.#3 5###.#..#..#.###

樣例輸出

63

題目意思：數羊群，上下左右四個方向，相連的即為一個羊群。

這題用深搜就可以了，比較簡單。

#include <stdio.h>int a,b,s;char m[101][101];	int dir[4][2]={1,0,0,1,-1,0,0,-1};void dfs(int x,int y){  	m[x][y]='.';	int i,xx,yy;   for(i=0;i<4;i++)   {   	xx=x+dir[i][0];   	yy=y+dir[i][1];   	if(xx>=0&&xx<a&&yy>=0&&yy<b&&m[xx][yy]=='#')    dfs(xx,yy);   }	}int main()//2777{	int i,j,u,w,t;	scanf("%d",&t);	while(t--)	{   scanf("%d%d",&a,&b);	    s=0;		if(a==0&&b==0)break;		for(i=0;i<a;i++)		scanf("%s",m[i]);					for(i=0;i<a;i++)		{			for(j=0;j<b;j++)			{				if(m[i][j]=='#')				{dfs(i,j);				s++;}			}		} 		printf("%d/n",s);		}}
TOJ 3834 Space Exploration
描述
Farmer John's cows have finally blasted off from earth and are now floating around space in their Moocraft. The cows want to reachtheir fiery kin on Jupiter's moon of Io, but to do this they must first navigate through the dangerous asteroid belt.
Bessie is piloting the craft through this treacherous N x N (1 <= N <= 1,000) sector of space. Asteroids in this sector comprise somenumber of 1 x 1 squares of space-rock connected along their edges (two squares sharing only a corner count as two distinct asteroids).Please help Bessie maneuver through the field by counting the number of distinct asteroids in the entire sector.Consider the 10 x 10 space shown below on the left. The '*'s represent asteroid chunks, and each '.' represents a .vast void of empty space. The diagram on the right shows an arbitrary numbering applied to the asteroids.
<span style="font-size:14px;"></span>
It's easy to see there are 7 asteroids in this sector.
輸入
* Line 1: A single integer: N* Lines 2..N+1: Line i+1 contains row i of the asteroid field: N characters
輸出
* Line 1: A single integer indicating the number of asteroids in the field.
樣例輸入
10...**......*..............*......*..*.....*****......*..........***....*..***........*...*..*.......
樣例輸出
7
題目意思：數牛群唄...和上面那題一樣的都是上下左右四個方向，但是這個地圖范圍是1000*1000，所以要用廣搜。
用廣搜一般都是隊列+結構體哦~
#include<cstdio>#include<cstring>#include<queue>using namespace std;int s,t;char m[1001][1001];	struct node{int x,y;};node pre,cur;int dir[4][2]={1,0,0,1,-1,0,0,-1};void bfs(int a,int b){    int i,x,y;    queue<node>que;    m[a][b]='.';    cur.x=a,cur.y=b;    que.push(cur);    while(!que.empty())    {        cur=que.front(),que.pop();        for(i=0;i<4;i++)        {            x=cur.x+dir[i][0];            y=cur.y+dir[i][1];            if(x>=0&&x<t&&y>=0&&y<t&&m[x][y]=='*')            {                m[x][y]='.';                pre.x=x,pre.y=y;                que.push(pre);            }        }            }}int main(){    int i,j,k;	s=0;	scanf("%d",&t);	for(i=0;i<t;i++)	scanf("%s",m[i]);	for(i=0;i<t;i++)	{		for(j=0;j<t;j++)		{			if(m[i][j]=='*')			{bfs(i,j);s++;}		}	} 	printf("%d/n",s);	}