fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7.  
  8. //COPY THE BLACKBOX, there is no need to change anything in it.
  9. //Check the main function at bottom for USAGE
  10.  
  11. //****************BLACKBOX START*****************
  12. //START COPYING FROM HERE
  13.  
  14. typedef int ll;
  15.  
  16. class Hash {
  17.   public:
  18.   	static int hash(int x){
  19.   		return hash({0,0,x});
  20.   	}
  21.   	static int hash(tuple<int,int>x){
  22.   		return hash({0,get<0>(x),get<1>(x)});
  23.   	}
  24.   	static int hash(tuple<int,int,int>x){
  25.   		int k=get<0>(x),u=get<1>(x),v=get<2>(x);
  26.   		return k*1873*1873 + u*1873 + v;
  27.   	}
  28. };
  29.  
  30. class Graph {
  31.  
  32. 	bool is_directed;
  33.  
  34. 	public:
  35. 		vector<vector<pair<int,ll>>>adj;
  36.     int n,N=2000000;
  37.  
  38. 		Graph(int n_, bool is_directed_){
  39. 			n=n_; is_directed = is_directed_;
  40. 			adj.resize(N,vector<pair<int,ll>>());
  41. 		}
  42.  
  43. 		int hash(int u, int v){
  44. 			return Hash::hash({u,v});
  45. 		}
  46. 		int hash(int u, int v, int k){
  47. 			return Hash::hash({u,v,k});
  48. 		}
  49.  
  50. 		void add_edge(int uR, int vR, ll c=0){
  51. 		  int u=Hash::hash(uR), v=Hash::hash(vR);
  52. 		  add_edge_internal(u,v,c);
  53. 		}
  54. 		void add_edge(tuple<int,int> uR, tuple<int,int> vR, ll c=0){
  55. 		  int u=Hash::hash(uR), v=Hash::hash(vR);
  56. 		  add_edge_internal(u,v,c);
  57. 		}
  58. 			void add_edge(tuple<int,int,int> uR, tuple<int,int,int> vR, ll c=0){
  59. 		  int u=Hash::hash(uR), v=Hash::hash(vR);
  60. 		  add_edge_internal(u,v,c);
  61. 		}
  62.  
  63.  
  64. 	private :
  65.  
  66. 	  void add_edge_internal(int u, int v, ll c=0){
  67. 			add_edge_weighted_undirected(u,v,c);
  68. 			if(!is_directed)
  69. 				add_edge_weighted_undirected(v,u,c);
  70. 		}
  71. 		void add_edge_weighted_undirected(int u, int v, ll c) {
  72. 			pair<int,ll>p = make_pair(v,c);
  73. 			adj[u].push_back(p);
  74. 		}
  75.  
  76. };
  77.  
  78. class BFS {
  79.     vector<ll>min_dist_from_source;
  80.     vector<bool> visited;
  81.     Graph *g;
  82.  
  83.     public:
  84.       BFS(Graph *g_) {
  85.           g = g_;
  86.           clear();
  87.       }
  88.  
  89. 	  	void clear() {
  90.   			min_dist_from_source.clear();
  91.   			min_dist_from_source.resize(g->N,-1);
  92.   			visited.clear();
  93.   			visited.resize(g->N, false);
  94.   		}
  95.  
  96.  
  97.       void run(int sourceR) {
  98.         int source = Hash::hash(sourceR);
  99.         run_internal(source);
  100.       }
  101.       void run(tuple<int,int> sourceR) {
  102.         int source = Hash::hash(sourceR);
  103.         run_internal(source);
  104.       }
  105.       void run(tuple<int,int,int> sourceR) {
  106.         int source = Hash::hash(sourceR);
  107.         run_internal(source);
  108.       }
  109.  
  110.  
  111.       int min_dist(int targetR){
  112.       	int target = Hash::hash(targetR);
  113.       	return min_dist_internal(target);
  114.       }
  115.       int min_dist(tuple<int,int> targetR){
  116.       	int target = Hash::hash(targetR);
  117.       	return min_dist_internal(target);
  118.       }
  119.       int min_dist(tuple<int,int,int> targetR){
  120.       	int target = Hash::hash(targetR);
  121.       	return min_dist_internal(target);
  122.       }
  123.  
  124.       bool is_visited(int targetR){
  125.       	int target = Hash::hash(targetR);
  126.       	return is_visited_internal(target);
  127.       }
  128.       bool is_visited(tuple<int,int> targetR){
  129.       	int target = Hash::hash(targetR);
  130.       	return is_visited_internal(target);
  131.       }
  132.       bool is_visited(tuple<int,int,int> targetR){
  133.       	int target = Hash::hash(targetR);
  134.       	return is_visited_internal(target);
  135.       }
  136.  
  137.   private:
  138.     void run_internal(int source) {
  139. 			queue<int> q;
  140. 			q.push(source);
  141.  
  142. 			visited[source] = true;
  143. 			min_dist_from_source[source] = 0;
  144.  
  145. 			while(!q.empty()) {
  146. 				int cur_node = q.front();
  147. 				for (unsigned int i = 0; i < (g->adj[cur_node]).size(); ++i) {
  148. 					int adj_node =  (g->adj[cur_node])[i].first;
  149. 					if (visited[adj_node] == false) {
  150. 						visited[adj_node] = true;
  151. 						min_dist_from_source[adj_node] = min_dist_from_source[cur_node] + 1;
  152. 						q.push(adj_node);
  153. 					}
  154. 				}
  155. 				q.pop();
  156. 			}
  157.  
  158. 			return;
  159.     }
  160.  
  161.     int min_dist_internal(int target){
  162.     	return min_dist_from_source[target];
  163.     }
  164.  
  165.     bool is_visited_internal(int target){
  166.     	return visited[target];
  167.     }
  168.  
  169. };
  170. //END COPYING HERE
  171. //********************BLACKBOX END******************
  172.  
  173. int main() {
  174.  
  175.     int n,m; cin>>n>>m;
  176.  
  177.     //initialise graph with `n*m` nodes, each cell is a node
  178.     Graph g(n*m,true);
  179.  
  180. 	//intiatialise a 2D array of size `n*m
  181.     vector<vector<char>>grid(n,vector<char>(m));
  182.  
  183.     for(int i=0;i<n;i++)
  184.       for(int j=0;j<m;j++){
  185.         cin>>grid[i][j];
  186.  
  187.       }
  188.  
  189.  
  190.    //************GRAPH CONTRUCTION BEGIN*****************
  191.  
  192.    //iterate through every cell
  193.     for(int i=0;i<n;i++)
  194.       for(int j=0;j<m;j++) {
  195.  
  196.       	//if current cell is floor
  197.         if(grid[i][j]=='.') {
  198.  
  199. 		// if cell above is withing the grid and a floor, create an Edge from `current cell -> cell above` 
  200.           if(i-1>=0 && grid[i-1][j]=='.') 
  201.             g.add_edge({i,j},{i-1,j});
  202.  
  203.         // if cell below is withing the grid and a floor, create an Edge from `current cell -> cell below` 	
  204.           if(i+1<n && grid[i+1][j]=='.') 
  205.             g.add_edge({i,j},{i+1,j});
  206.  
  207. 		// if cell left is withing the grid and a floor, create an Edge from `current cell -> cell left` 
  208. 		  if(j-1>=0 && grid[i][j-1]=='.')
  209.             g.add_edge({i,j},{i,j-1});
  210.  
  211.          // if cell right is withing the grid and a floor, create an Edge from `current cell -> cell right` 
  212.           if(j+1<m && grid[i][j+1]=='.')
  213.             g.add_edge({i,j},{i,j+1});
  214.         }
  215.       }
  216.       //************GRAPH CONTRUCTION END*****************
  217.  
  218.  
  219.    //Since the number of nodes is high, and the Blackbox BFS returns the vector min_dist of size 'n*m', returning an array of size x takes time x. We might get TLE as the BFS is being called multiple times, requiring returning min_dist multiple times.
  220.    //Therefore we need to go into the Blackbox and return the pointer to the min_dist instead of the whole array. Returning a point take 1 unit time only.
  221.  
  222.  
  223.    int num_rooms=0;
  224.  
  225.    BFS bfs(&g);
  226.    //iterate through every cell
  227.     for(int i=0;i<n;i++)
  228.       for(int j=0;j<m;j++){
  229.     	//if the current cell is not reachable from any of the cell we already iterated, then we have found a new room	
  230.       if(!bfs.is_visited({i,j}) && grid[i][j]=='.'){
  231.         num_rooms++;
  232.  
  233.        //BFS from `i,j` will visit every cell reachable from `i,j`, aka in the same connected component(room) as `i,j`
  234.         //`min_dist[k]` for all the nodes reachable from `i,j` will be the shortest path length from node `i,j` to node `k`
  235.         bfs.run({i,j});
  236.       }
  237.     }
  238.  
  239.  
  240.     cout<<num_rooms<<'\n';
  241.  
  242.     return 0;
  243.  
  244.  
  245.   }
Success #stdin #stdout 0.03s 57952KB
comments (?)
stdin 
5 8
########
#..#...#
####.#.#
#..#...#
########
stdout 
3
https://ideone.com/oZJxIF
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!