HDU 1241 石油储蓄 (简单DFS)
最近几天开始做简单的搜索题 做的杭电的 1010,2040,2041
这是2041的题目和代码,上课时候在纸上写了一遍,对这个模板不熟悉,还是参考了大神们的标准代码。
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either *', representing the absence of oil, or
@’, representing an oil pocket.
Output
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
Sample Input
1 1
*
3 5
@@*
@
@@*
1 8
@@***@
5 5
****@
@@@
@**@
@@@@
@@**@
0 0
Sample Output
0
1
2
2
题意
有n*m的表,*是空地,@代表有石油
互相连通的石油算一种,要求他有多少种石油;
连通的话,算上下左右,还有四个对角线。
先枚举map里每一个元素,如果是@,计数就加一,
调用dfs将与其相连通的全修改成*
#include<stdio.h>
char map [101][101];
int mx[8]={0,0,1,-1,1,1,-1,-1};
int my[8]={1,-1,0,0,-1,1,1,-1};
void dfs(int x,int y)
{
map[x][y]='*';//更改其标志,防止重复计算
int dx,dy;
for(int i=0;i<8;i++)
{
dx=x+mx[i];
dy=y+my[i];
if(map[dx][dy]=='@')
{
dfs(dx,dy);
}
}
}
int main()
{
int n,m;
while (scanf("%d %d",&n,&m)!=EOF)
{
if(m==0||n==0)
break;
int sum=0;
for(int i=0;i<n;i++)
scanf("%s",map[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(map[i][j]=='@')
{
dfs(i,j);
sum++;
}
}
}
printf("%d\n",sum);
}
return 0;
}
下一篇: ACM PKU 3067 Japan