acm入门搜索-石油数目

题意：给出一个N*M的矩形区域和每个区域的状态--有/没有石油，（定义）如果两个有石油的区域是相邻的（水平、垂直、斜）则认为这是属于同一个oil
pocket。

求这块矩形区域一共有多少oilpocket

#include <stdio.h>
int grid[101][101];
char s[102][102];
int m,n;
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
void dfs(int x,int y)
{
    int i,xx,yy;
    grid[x][y]=0;
    for(i=0;i<4;i++)
    {
        xx=x+dir[i][0];
        yy=y+dir[i][1];
        if(xx<0||yy<0||x>m||y>=n)
        continue;
        if(grid[xx][yy]==1)
        dfs(xx,yy);
    }
}

int main()
{
	int i, j, sum;
	while(scanf("%d%d", &m, &n), m)
	{
		for(i = 0; i < m; i++)
			scanf("%s", s+i);
		for(i = sum = 0; i < m; i++)
			for(j = 0; j < n; j++)
			{
				if(s[i][j] == '@')
				{
					sum++;
					dfs(i, j);
				}
			}
		printf("%d\n", sum);
	}
	return 0;
}

巴特西

acm入门搜索-石油数目

最新文章

热门文章