Guest User

Untitled

a guest
Mar 10th, 2022
403
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | None | 0 0
  1. // Super Idol的笑容
  2. //    都没你的甜
  3. //  八月正午的阳光
  4. //    都没你耀眼
  5. //  热爱105°C的你
  6. // 滴滴清纯的蒸馏水
  7.  
  8. #include <bits/stdc++.h>
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. #include <ext/pb_ds/tree_policy.hpp>
  11. #include <ext/rope>
  12. using namespace std;
  13. using namespace __gnu_pbds;
  14. using namespace __gnu_cxx;
  15. #define int long long
  16. #define ll long long
  17. #define ii pair<ll,ll>
  18. #define iii pair<ii,ll>
  19. #define fi first
  20. #define se second
  21. #define endl '\n'
  22. #define debug(x) cout << #x << ": " << x << endl
  23.  
  24. #define pub push_back
  25. #define pob pop_back
  26. #define puf push_front
  27. #define pof pop_front
  28. #define lb lower_bound
  29. #define ub upper_bound
  30.  
  31. #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
  32. #define all(x) (x).begin(),(x).end()
  33. #define sz(x) (int)(x).size()
  34.  
  35. #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
  36. //change less to less_equal for non distinct pbds, but erase will bug
  37.  
  38. mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
  39.  
  40. const int S=2005;
  41.  
  42. int n,m;
  43. string inp[2005];
  44. char grid[S+5][S+5];
  45. bool vis[S+5][S+5];
  46.  
  47. const int dx[]={0,0,-1,1};
  48. const int dy[]={-1,1,0,0};
  49.  
  50. int a,b,c,d;
  51. int cnt;
  52.  
  53. void dfs(int i,int j){
  54.     vis[i][j]=true;
  55.     a=min(a,i-j),b=max(b,i-j);
  56.     c=min(c,i+j),d=max(d,i+j);
  57.     cnt++;
  58.    
  59.     rep(z,0,4){
  60.         int aa=i+dx[z],bb=j+dy[z];
  61.         if (aa<0 || S<=aa || bb<0 || S<=bb || vis[aa][bb] || grid[aa][bb]=='#') continue;
  62.         dfs(aa,bb);
  63.     }
  64. }
  65.  
  66. signed main(){
  67.     ios::sync_with_stdio(0);
  68.     cin.tie(0);
  69.     cout.tie(0);
  70.     cin.exceptions(ios::badbit | ios::failbit);
  71.    
  72.     cin>>n>>m;
  73.     rep(x,0,n) cin>>inp[x];
  74.    
  75.     memset(grid,'.',sizeof(grid));
  76.    
  77.     rep(x,0,n) rep(y,0,m) grid[x+1][y+1]=inp[x][y];
  78.    
  79.     dfs(0,0);
  80.    
  81.     int ans=0;
  82.     rep(x,1,n+1) rep(y,1,m+1) if (grid[x][y]=='.' && !vis[x][y]){
  83.         a=c=1e9;
  84.         b=d=-1e9;
  85.         cnt=0;
  86.        
  87.         dfs(x,y);
  88.        
  89.         if ((b-a+1)==(d-c+1) && (b-a+1)*(d-c+1)==cnt*2-1) ans++;
  90.     }
  91.    
  92.     cout<<ans<<endl;
  93. }
  94.  
Advertisement
Add Comment
Please, Sign In to add comment