fireLUFFY

CSES_CountingRooms

May 12th, 2021 (edited)
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.33 KB | None | 0 0
  1. // fireLUFFYY
  2.  
  3. #pragma GCC optimize("Ofast")
  4. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
  5. #pragma GCC optimize("unroll-loops")
  6. #pragma comment(linker, "/stack:200000000")
  7.  
  8. #include<bits/stdc++.h>
  9.  
  10. #define int long long
  11. #define ull unsigned long long
  12. #define vi vector<int>
  13. #define vvl vector<vector<int>>
  14. #define deql deque<int>
  15. #define prquel priority_queue<int>
  16. #define loop(i,n) for(int i=0;i<n;i++)
  17. #define loopn(i,a,b) for(int i=a;i<=b;i++)
  18. #define rloop(i,n) for(int i=n;i>0;i--)
  19. #define sortv(a) sort(a.begin(),a.end())
  20. #define sortvr(a) sort(a.rbegin(),a.rend())
  21. #define verase(a) a.erase(unique(a.begin(),a.end()),a.end())
  22. #define all(a) a.begin(),a.end()
  23. #define dbg(x) cout<<#x<<" = "<<x<<"\n";
  24. #define mp make_pair
  25. #define pb push_back
  26. #define pf push_front
  27. #define fi first
  28. #define se second
  29. #define endl "\n"
  30. #define inf 2e18
  31. using namespace std;
  32.  
  33. int MOD=1000000007;
  34. int mod=998244353;
  35. const int N=200050;
  36. const int nn=1000050;
  37. int fact[N]; // array to store values of factorial
  38. bool prime[nn]; //array to store precalculated primes till 10^6
  39. bool pow2(int x){if(x&&(!(x&(x-1)))) return true; else return false;}
  40. int gcd(int a,int b) { if(a == 0)return b;return gcd(b % a, a);}
  41. int lcm(int a,int b){int val=max(a,b)/gcd(a,b);val*=min(a,b);return val;}
  42. int multiply(int x, int y){return (x * 1ll * y) % MOD;}
  43. int power(int x, int y){int z = 1;while(y){if(y & 1) z = multiply(z, x);x = multiply(x, x);y >>= 1;}return z;}
  44. int modInverse(int x){return power(x, MOD - 2);}
  45. int divide(int x, int y){return multiply(x, modInverse(y));}
  46. void cal_factorial(){fact[0] = 1;for(int i = 1; i < N; i++)fact[i] = multiply(fact[i - 1], i);}// function to calculate factorial upto N
  47. void cal_primes(){memset(prime,true,sizeof(prime)); loopn(i,2,sqrt(nn)){ if(prime[i]==true){ for(int j=i*i;j<=nn;j+=i){prime[j]=false;}}}}
  48. int nCr(int n, int k){return divide(fact[n], multiply(fact[k], fact[n - k]));}
  49. void FASTIO(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
  50.  
  51. int dx[]={0,1,0,-1};
  52. int dy[]={1,0,-1,0};
  53. bool trav(int x,int y,int n,int m)
  54. {
  55.     if((x<n)&&(x>=0)&&(y<m)&&(y>=0))
  56.         return true;
  57.     else
  58.         return false;
  59. }
  60.  
  61. void dfs(vvl grid,int r,int c,int n,int m,vector<vector<bool>> vis)
  62. {
  63.     vis[r][c]=true;
  64.     loop(i,4)
  65.     {
  66.         if((trav((r+dx[i]),(c+dy[i]),n,m))&&(grid[r+dx[i]][c+dy[i]])&&(!vis[r+dx[i]][c+dy[i]]))
  67.             dfs(grid,(r+dx[i]),(c+dy[i]),n,m,vis);
  68.     }
  69. }
  70. void solve(int t)
  71. {
  72.     int testcases=t;
  73.     while(t--)
  74.     {
  75.         //cout<<"#"<<(testcases-t)<<" Test-Case: "<<endl;
  76.         int n,m;
  77.         cin>>n>>m;
  78.         cin.ignore();
  79.         vector<vector<int>> grid(n,vector<int>(m,0));
  80.         string s;
  81.         loop(i,n)
  82.         {
  83.             cin>>s;
  84.             loop(j,m)
  85.             {
  86.                 if(s[j]=='.')
  87.                     grid[i][j]=1;
  88.                 else
  89.                     grid[i][j]=0;
  90.             }
  91.         }
  92.         vector<vector<bool>> vis(n,vector<bool>(m,false));
  93.         int cnt=0;
  94.         loop(i,n)
  95.         {
  96.             loop(j,m)
  97.             {
  98.                 if((grid[i][j])&&(!vis[i][j]))
  99.                 {
  100.                     dfs(grid,i,j,n,m,vis);
  101.                     cnt++;
  102.                 }
  103.             }
  104.         }
  105.         cout<<cnt<<endl;
  106.     }
  107. }
  108.  
  109. main()
  110. {
  111.     auto start=chrono::system_clock::now();
  112.     {
  113.         #ifndef ONLINE_JUDGE
  114.             freopen("input.txt","r",stdin);
  115.             freopen("output.txt","w",stdout);
  116.         #endif
  117.         FASTIO();  
  118.         int t=1;
  119.     //  cin>>t;
  120.         solve(t);
  121.     }
  122.     auto end=chrono::system_clock::now();
  123.     chrono::duration<double> elapsed=end-start;
  124. //  cout<<" Time taken: "<<elapsed.count()<<" sec";
  125.     return 0;
  126. }
Add Comment
Please, Sign In to add comment