原题
题意
油田为@，普通地为*,若一个@周围8个方位内还有@则为同一片油田，问总共多少个油田
分析
DFS，对整个矩阵进行爆搜，在整个矩阵中，遇到一个@，将当前@变为，油田数num++，然后由此开始dfs周围，对每遇到的一个@，将其变为，并继续dfs直到没有@回溯。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
using namespace std;
int m,n;
string a[107];
void dfs(int i,int j){
int ni,nj;
for(int p=-1;p<=1;p++){
for(int q=-1;q<=1;q++){
ni=i+p;
nj=j+q;
if(ni>=0&&ni<m&&nj>=0&&nj<n){
if(a[ni][nj]=='@'){
a[ni][nj]='*';
dfs(ni,nj);
}
}
}
}
}
int main()
{
int num;
while(scanf("%d%d",&m,&n)!=EOF){
if(m==0||n==0){
break;
}
for(int i=0;i<m;i++){
cin>>a[i];
}
num=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='@'){
a[i][j]='*';
dfs(i,j);
num++;
}
}
}
printf("%d\n",num);
}
return 0;
}
|
