HDU 1241 Oil Deposits DFS搜索题

时间:2023-03-09 18:51:35
HDU 1241 Oil Deposits DFS搜索题

题目大意:给你一个m*n的矩阵,里面有两种符号,一种是 @ 表示这个位置有油田,另一种是 * 表示这个位置没有油田,现在规定相邻的任意块油田只算一块油田,这里的相邻包括上下左右以及斜的的四个方向相邻的位置。要你求出一共有多少块油田。

解题报告:用dfs,我的做法是首先在输入的时候将每个有油田的位置标记为1,否则标记为0,然后枚举每一个点,如果这个点有油田,则以这个点为起点,像周围的八个方向搜索,搜到了相邻的点就标记为2,当然这里也可以标记为0,只要是将已经搜过的点标记掉就是了,当dfs退出到main函数的时候,油田数量加一。

 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
const int MAX = +;
int m,n,map[MAX][MAX],num;
int dire[][] = {{-,},{-,},{,},{,},{,},{,-},{,-},{-,-}};
void dfs(int x,int y) {
if(map[x][y] == ) {
map[x][y] = ;
for(int i = ;i<;++i) {
int xx = x + dire[i][];
int yy = y + dire[i][];
if(xx<||xx>m||yy<||yy>n)
continue;
dfs(xx,yy);
}
}
} int main() {
char c,shu[MAX][MAX];
while(scanf("%d%d",&m,&n),m+n) {
memset(map,,sizeof(map));
for(int i = ;i<=m;++i) {
getchar();
for(int j = ;j<=n;++j) {
scanf("%c",&c);
if(c == '@')
map[i][j] = ;
}
}
int ans = ;
for(int i = ;i<=m;++i)
for(int j = ;j<=n;++j)
if(map[i][j] == ) {
dfs(i,j);
ans++;
}
printf("%d\n",ans);
}
return ;
}