fork download 
  1. #include<bits/stdc++.h>
  2. #define INF 1073741824
  3. #define ll long long
  4. #define PI (2*acos(0.0))
  5. #define p1(n) printf("showing %d\n",n)
  6. #define p2(m,n) printf("showing %d %d\n",m,n)
  7. #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
  8. #define mp make_pair
  9. #define pb push_back
  10. #define pii pair<int,int>
  11. #define pll pair<ll,ll>
  12. #define x first
  13. #define y second
  14. #define on(val,pos) val|(1<<pos)
  15. #define off(val,pos) val&(~(1<<pos))
  16. #define check(val,pos) (val&(1<<pos))
  17. #define all(n) n.begin(),n.end()
  18. //first four adjacent,second four corner
  19. int row[8]={0,-1,0,1,1,-1,-1,1};
  20. int col[8]={-1,0,1,0,-1,-1,1,1};
  21. using namespace std;
  22. string s[1001];
  23. int n,m;
  24. bool southpole(bool row[],bool col[]){
  25.     int i,j;
  26.     for(i=0;i<n;i++){
  27.         if(row[i]==false){
  28.             for(j=0;j<m;j++) if(col[j]==false)break;
  29.             if(j==m)break;
  30.         }
  31.     }
  32.     if(i<n)return true;
  33.     for(i=0;i<m;i++){
  34.         if(col[i]==false){
  35.             for(j=0;j<n;j++) if(row[j]==false)break;
  36.             if(j==n)break;
  37.         }
  38.     }
  39.     if(i<m)return true;
  40.     else return false;
  41. }
  42. bool northpole(){
  43.     for(int i=0;i<n;i++){
  44.         int p=0,q=m-1;
  45.         while(s[i][p]!='#' and p<m)p++;
  46.         while(s[i][q]!='#' and q>=0)q--;
  47.         if(p<q){
  48.             while(p<q and s[i][p]=='#')p++;
  49.             if(p<q)return true;
  50.         }
  51.     }
  52.     for(int i=0;i<m;i++){
  53.         int p=0,q=n-1;
  54.         while(p<n and s[p][i]!='#')p++;
  55.         while(q>=0 and s[q][i]!='#')q--;
  56.  
  57.         if(p<q){
  58.             while(p<q and s[p][i]=='#')p++;
  59.             if(p<q)return true;
  60.         }
  61.     }
  62.  
  63.     return false;
  64. }
  65. map<pii,bool> checked;
  66.  
  67. queue<pii>que;
  68.  
  69.  
  70. void BFS(pii node){
  71.     checked[node]=true;
  72.  
  73.     que.push(node);
  74.     while(!que.empty()){
  75.         pii cur=que.front();
  76.         que.pop();
  77.  
  78.         for(int i=0;i<4;i++){
  79.             int j=cur.x+row[i],k=cur.y+col[i];
  80.             if(j>=0 and k>=0 and j<n and k<m and s[j][k]=='#' and checked[{j,k}]==false){
  81.                 checked[{j,k}]=true;
  82.  
  83.                 que.push({j,k});
  84.  
  85.             }
  86.         }
  87.     }
  88. }
  89.  
  90. int main(){
  91.     int i,j,k,val,t=0,test;
  92.     //freopen("000input.txt","r",stdin);
  93.  
  94.         cin>>n>>m;
  95.         for(i=0;i<n;i++)cin>>s[i];
  96.         bool row[n],col[m];
  97.         for(i=0;i<n;i++){
  98.             for(j=0;j<m;j++){
  99.                 if(s[i][j]=='#')row[i]=true,col[j]=true;
  100.             }
  101.         }
  102.         ///South pole placement check &
  103.         ///north pole not enter forbidden cell check
  104.         if(southpole(row,col) or northpole()){
  105.             printf("-1\n");
  106.         }
  107.  
  108.         else{
  109.             int cnt=0;
  110.             for(i=0;i<n;i++){
  111.                 for(j=0;j<m;j++){
  112.                     if(s[i][j]=='#' and checked[{i,j}]==false){
  113.                         cnt++;
  114.                         BFS({i,j});
  115.                     }
  116.                 }
  117.             }
  118.             printf("%d\n",cnt);
  119.         }
  120.  
  121.     //free();   //if pointer array
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0s 4384KB
comments (?)
stdin 
2 1
.
#
stdout 
-1
https://ideone.com/1YmrBg
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!