fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N=2002;
  5. int maze[N][N], visited[N][N];
  6. int n,m;
  7. int dx[]={0,0,-1,1};
  8. int dy[]={1,-1,0,0};
  9.  
  10. bool is_inside(pair<int,int>coord)
  11. {
  12.     int x=coord.first;
  13.     int y=coord.second;
  14.  
  15.     if(x>=0 && x<n && y>=0 && y<m)
  16.     {
  17.         return true;
  18.     }
  19.     return false;
  20. }
  21.  
  22. bool is_safe(pair<int,int>coord)
  23. {
  24.     int x= coord.first;
  25.     int y = coord.second;
  26.  
  27.     if(maze[x][y]=-1)
  28.     {
  29.         return false;
  30.     }
  31.     return true;
  32. }
  33.  
  34. void bfs(pair<int,int>src)
  35. {
  36.     queue<pair<int,int>>q;
  37.     visited[src.first][src.second]=1;
  38.     q.push(src);
  39.     while(!q.empty())
  40.     {
  41.         pair<int,int>head = q.front();
  42.         q.pop();
  43.         int x=head.first;
  44.         int y = head.second;
  45.  
  46.         for(int i=0;i<4;i++)
  47.         {
  48.             int new_x=x+dx[i];
  49.             int new_y = y+dy[i];
  50.             pair<int,int>adj_node = {new_x,new_y};
  51.             if(is_inside(adj_node) && is_safe(adj_node) && visited[new_x][new_y]==0)
  52.             {
  53.                 visited[new_x][new_y]=1;
  54.                 q.push(adj_node);
  55.             }
  56.         }
  57.     }
  58.  
  59. }
  60. pair<int,int>find_unvisited() 
  61. {
  62.     for(int i=0;i<n;i++)
  63.     {
  64.         for(int j=0;j<m;j++)
  65.         {
  66.             if(visited[i][j]==0 && maze[i][j]==0)
  67.             {
  68.                 return{i,j};
  69.             }
  70.         }
  71.     }
  72.     return {-1,-1};
  73. }
  74.  
  75.  
  76. int main()
  77. {
  78.     cin>>n>>m;
  79.     for(int i=0;i<n;i++)
  80.     {
  81.         string input;
  82.         cin>>input;
  83.  
  84.         for(int j=0;j<m;j++)
  85.         {
  86.             if(input[j]=='#')
  87.             {
  88.                 maze[i][j]=-1;
  89.             }
  90.         }
  91.     }
  92. //    for(int i=0;i<n;i++)
  93. //    {
  94. //        for(int j=0;j<m;j++)
  95. //        {
  96. //            cout<<maze[i][j]<<"\t";
  97. //        }
  98. //        cout<<endl;
  99. //    }
  100. //    cout<<endl;
  101.  
  102.     int room_cnt = 0;
  103.     while(true)
  104.     {
  105.         pair<int,int>unvisited_pos = find_unvisited();
  106.         if(unvisited_pos == pair<int,int>(-1,-1))
  107.         {
  108.             break;
  109.         }
  110.         bfs(unvisited_pos);
  111.         room_cnt++;
  112.     }
  113.     cout<<room_cnt<<endl;
  114.  
  115.  
  116.  
  117. }
  118.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/EzflGq
language:
C++ (gcc 8.3)
created:
1 year 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!