[UVA] 572 - Oil Deposits

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [UVA] 572  -  Oil Deposits
Source            : UVA Online Judge
Category          : Graph Theory
Algorithm         : DFS
Verdict           : Accepted

1. #include<bits/stdc++.h>  
2. using namespace std;  
3. #define mp(a,b) make_pair(a,b)  
4. #define mem(a,v) memset(a,v,sizeof(a))  
5. int dx8[]={1,1,1,0,-1,-1,-1,0};  
6. int dy8[]={-1,0,1,1,1,0,-1,-1};  
7. char str[105][105];  
8. map<pair<int,int>,int>visit;  
9. void dfs(int a,int b){  
10.     int x,y;  
11.     visit[mp(a,b)]=1;  
12.     for(int i=0;i<8;i++){  
13.         x=a+dx8[i];  
14.         y=b+dy8[i];  
15.         if(str[x][y]=='@' && !visit[mp(x,y)]){  
16.             dfs(x,y);  
17.         }  
18.     }  
19. }  
20. int main () {  
21.   
22.     //freopen("input.txt","r",stdin);  
23.     //freopen("output.txt","w",stdout);  
24.     int r,c;  
25.     while(cin>>r>>c){  
26.         if(r==0 && c==0)break;  
27.         mem(str,0);  
28.         for(int i=0;i<r;i++){  
29.             cin>>str[i];  
30.         }  
31.         visit.clear();  
32.         int cnt=0;  
33.         for(int i=0;i<r;i++){  
34.             for(int j=0;j<c;j++){  
35.                 if(str[i][j]=='@' && !visit[mp(i,j)]){  
36.                     cnt++;  
37.                     dfs(i,j);  
38.                 }  
39.             }  
40.         }  
41.         cout<<cnt<<endl;  
42.     }  
43.     return 0;  
44. }