fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define f first
  6. #define s second
  7. #define pb push_back
  8. #define sz(v) ((int)v.size())   
  9. #define rad(a) a * PI / 180  
  10.  
  11. typedef long long ll;
  12. typedef vector<int> vi;	
  13. typedef pair<int,int> ii;
  14. typedef pair<int,char> ic;
  15. typedef pair<ll, bool> llb;
  16.  
  17. const int SIGMA = 300;
  18. const int MAX = 1000010;
  19. const int MAXT = 1200010;
  20. const int INF = 300000;
  21. const int P = 1000000007;
  22. const double EPS = 1e-6;
  23. const double PI = 3.14159265358979;
  24.  
  25. const int UNVISITED = -1;
  26.  
  27. int n, m;
  28. vector<string> mat;
  29. void read(){
  30. 	cin >> n >> m;
  31. 	string row;
  32.  
  33. 	for(int i = 0; i < n; i++){
  34. 		cin >> row;
  35. 		mat.pb(row);	
  36. 	}
  37. }
  38.  
  39. int di[] = {1, 0}, dj[] = {0, 1};
  40.  
  41. vector<int> graph[MAX];
  42. void build_graph(){
  43.  
  44. 	for(int i = 0; i < n; i++){
  45. 		for(int j = 0; j < m; j++){
  46. 			if(mat[i][j] == '#') continue;
  47.  
  48. 			int v = i*m + j;
  49. 			for(int k = 0; k < 2; k++){
  50. 				int ni = i+di[k];
  51. 				int nj = j+dj[k];
  52.  
  53. 				if(0 <= ni && ni < n && 
  54. 					0 <= nj && nj < m &&
  55. 				 	mat[ni][nj] == '.' ){
  56. 					int u = ni*m + nj;
  57.  
  58. 					graph[u].pb(v);
  59. 					graph[v].pb(u);
  60. 				}
  61. 			}
  62. 		}
  63. 	}
  64. }
  65.  
  66. int dfs_counter, rootChild;
  67. int dfs_num[MAX], dfs_low[MAX];
  68. set<int> artVert;
  69. void dfs(int u, int p){
  70. 	dfs_num[u] = dfs_low[u] = dfs_counter++;
  71. 	for(int i = 0; i < sz(graph[u]); i++){
  72. 		int v = graph[u][i];
  73.  
  74. 		if(dfs_num[v] == UNVISITED){
  75. 			if(p == -1) rootChild++;
  76.  
  77. 			dfs(v, u);
  78.  
  79. 			if(dfs_low[u] <= dfs_low[v]){
  80. 				artVert.insert(u);
  81. 			}
  82.  
  83. 			dfs_low[u] = min(dfs_low[u], dfs_low[v]);
  84. 		}
  85. 		else if(v != p){
  86. 			dfs_low[u] = min(dfs_low[u], dfs_num[v]);
  87. 		}
  88. 	}	
  89. }
  90.  
  91. void find_art_vert(){
  92. 	for(int i = 0; i < MAX; i++){
  93. 		dfs_num[i] = dfs_low[i] = UNVISITED;
  94. 	}
  95.  
  96. 	dfs_counter = 0;
  97. 	for(int i = 0; i < MAX; i++){
  98. 		if(dfs_num[i] == UNVISITED){
  99. 			rootChild = 0;
  100. 			dfs(i, -1);	
  101. 			if(rootChild == 0) continue;
  102. 			if(rootChild == 1) artVert.erase(i);
  103. 			else artVert.insert(i);
  104. 		}
  105. 	}
  106. }
  107.  
  108. int component[MAX];
  109. void dfs2(int u, int comp){
  110. 	component[u] = comp;
  111. 	for(int i = 0; i < sz(graph[u]); i++){
  112. 		int v = graph[u][i];
  113. 		if(component[v] == UNVISITED && artVert.find(v) == artVert.end()){
  114. 			dfs2(v, comp);
  115. 		}
  116. 	}
  117. }
  118.  
  119. void find_components(){
  120. 	for(int i = 0; i < MAX; i++){
  121. 		component[i] = UNVISITED;
  122. 	}	
  123.  
  124. 	int comp = 0;
  125. 	for(int i = 0; i < MAX; i++){
  126. 		if(component[i] == UNVISITED){
  127. 			dfs2(i, comp++);
  128. 		}
  129. 	}
  130. }
  131.  
  132. set<int> vis;
  133. void dfs3(int i, int j){
  134. 	vis.insert(i*m+j);
  135. 	for(int k = 0; k < 2; k++){
  136. 		int ni = i+di[k];
  137. 		int nj = j+dj[k];
  138.  
  139. 		if(0 <= ni && ni < n && 
  140. 			0 <= nj && nj < m &&
  141. 		 	mat[ni][nj] == '.' &&
  142. 			vis.find(ni*m + nj) == vis.end() ){
  143. 			dfs3(ni,nj);
  144. 		}
  145. 	}
  146. }
  147.  
  148. bool no_path(){
  149. 	dfs3(0,0);
  150. 	return vis.find((n-1)*m + m-1) == vis.end();
  151. }
  152.  
  153.  
  154. int main(){
  155. 	ios::sync_with_stdio(false);
  156. 	cin.tie(nullptr);
  157. 	cout.tie(nullptr);
  158.  
  159. 	read();
  160.  
  161. 	if(no_path()){
  162. 		printf("0\n");
  163. 		return 0;
  164. 	}
  165.  
  166. 	build_graph();			
  167.  
  168. 	find_art_vert();
  169.  
  170. 	find_components();
  171.  
  172. 	int end = (n-1)*m + m-1;	
  173. 	if(component[end] != component[0]){
  174. 		printf("1\n");			
  175. 	}
  176. 	else{
  177. 		printf("2\n");
  178. 	}
  179.  
  180. 	return 0;
  181. }
Success #stdin #stdout 0.02s 38676KB
comments (?)
stdin
copy 
3 5
.....
.....
#.#..
stdout
copy 
1
https://ideone.com/gc6HOQ
language:
C++14 (gcc 8.3)
created:
5 years 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!