Advertisement
Guest User

Untitled

a guest
Dec 19th, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. using namespace std;
  6. vector < vector<int> > g1(100);
  7. vector<int> used;
  8. void dfs (int v) {
  9.     used[v] = 1;
  10.     for (int i = 0 ; i < int(g1[v].size()); ++i)
  11.         if (!used[g1[v][i]])
  12.             dfs (g1[v][i]);
  13. }
  14. int main() {
  15.     ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  16.     int n;cin >> n;int p=1;
  17.     int m;cin >> m; int a[101][101]={0};
  18.     for(int i = 0 ; i < n; i++)
  19.     for(int j = 0 ; i < m; j++){
  20.         char x; cin >> x;
  21.         if(x == 'O'){ a[i][j] = p;p++;}
  22.     }
  23.     for(int i = 0; i < p;i++) used.push_back(0);
  24. for(int i = 0 ; i < n; i++)
  25.     for(int j = 0 ; i < m; j++){
  26.         if(a[i][j] != 0){
  27.          if( j-1>=0 && a[i][j-1] !=0){
  28.             g1[a[i][j]].push_back(a[i][j-1]);
  29.             g1[a[i][j-1]].push_back(a[i][j]);    
  30.           }
  31.           if( j+1<m && a[i][j+1] !=0){
  32.             g1[a[i][j]].push_back(a[i][j+1]);
  33.             g1[a[i][j+1]].push_back(a[i][j]);    
  34.           }
  35. if( i-1>=0 && a[i-1][j] !=0){
  36.             g1[a[i][j]].push_back(a[i-1][j]);
  37.             g1[a[i-1][j]].push_back(a[i][j]);    
  38.           }
  39. if( i+1<n && a[i+1][j] !=0){
  40.             g1[a[i][j]].push_back(a[i+1][j]);
  41.             g1[a[i+1][j]].push_back(a[i][j]);    
  42.           }
  43.  
  44.  
  45.       }
  46.     }
  47.     int k = 0;
  48.  
  49.     for(int i = 0; i < p; i++){
  50.         if(used[i] == 0){ dfs(i); k++;}
  51.     }
  52.     cout << k;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement