fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6. inline int power(int a, int b) {
  7.     int x = 1;
  8.     while (b) {
  9.         if (b & 1) x *= a;
  10.         a *= a;
  11.         b >>= 1;
  12.     }
  13.     return x;
  14. }
  15.  
  16.  
  17. const int M = 1000000007;
  18. const int N = 3e5+9;
  19. const int INF = 2e9+1;
  20. const int LINF = 2000000000000000001;
  21.  
  22. //_ ***************************** START Below *******************************
  23.  
  24. vector<vector<int>> a;
  25. vector<vector<int>> dirs = {{0, 1} , {1, 0} , {0, -1}, {-1, 0} };
  26. queue<pair<int,int>> q;
  27. vector<vector<bool>> visited;
  28. vector<vector<int>> lvl;
  29.  
  30. void dfs(int x, int y, int m, int n){
  31.  
  32. 	visited[x][y] = true;
  33. 	a[x][y] = 2;
  34.  
  35. 	bool anyChildZero = false;
  36. 	for(auto& dir : dirs){
  37. 		int i = x + dir[0];
  38. 		int j = y + dir[1];
  39.  
  40. 		if(i<0 || i>=m || j<0 || j>=n) continue;
  41. 		if(a[i][j] == 0) anyChildZero = true;
  42.  
  43. 		if(a[i][j] == 0 || visited[i][j]) continue;
  44. 		dfs(i, j, m, n);
  45. 	}
  46.  
  47. 	if(anyChildZero) q.push({x,y});
  48.  
  49. }
  50.  
  51.  
  52. //* Eg : 
  53. //* 	0 0 0 0 0 0 0 
  54. //* 	0 1 1 1 0 0 0
  55. //* 	0 1 0 1 0 0 0 
  56. //* 	0 1 1 1 0 0 0 
  57. //* 	0 0 0 0 0 1 1
  58. //* 	0 0 0 0 1 1 1
  59. //* 	0 0 0 0 0 1 0
  60.  
  61. //? Interview Approach  : 
  62. //* 	Do bfs from all nodes of Island 1 (i.e. internal nodes also )
  63.  
  64. //* Optimized Approach : 
  65. //* 	We are only interested in distance from boundary of island 1 to all other nodes
  66. //* 	Do bfs from Boundary nodes only of Island 1
  67. //* 	Even if bfs find distance of inside nodes of Island 1 , we don tcare, 
  68. //* 		we only calculate ans for island 2 later while traversing
  69.  
  70.  
  71. //* How to BFS island 1 ? 
  72. //* 	1. Store all nodes of island 1 in Hashmap 
  73. //* 	   Do boundary bfs from boundary nodes only
  74. //* 	   Island 2 nodes can be identified in O(1) check using Hashmap
  75. //* 					OR		
  76. //* 	2. Color the nodes of island 1 (inplace or with separate matrix)
  77. //* 		Island 2 can be identified with a[i][j] == 1 (2 is for Island 1)
  78.  
  79.  
  80. void consistency(int m, int n){
  81.  
  82. 	visited.resize(m, vector<bool>(n, false));
  83. 	lvl.resize(m, vector<int>(n, 0));
  84.  
  85. 	for(int i=0; i<m; i++){
  86. 		bool isFirstIslandTraversed = false;
  87. 		for(int j=0; j<n; j++){
  88. 			if(a[i][j] == 1) {
  89. 				dfs(i,j, m, n);
  90. 				isFirstIslandTraversed = true;
  91. 				break;
  92. 			}
  93. 		}
  94. 		if(isFirstIslandTraversed) break;
  95. 	}
  96.  
  97.  
  98. 	int mini = INF;
  99.  
  100. 	while(!q.empty()){
  101.  
  102. 		auto u = q.front(); q.pop();
  103.  
  104. 		int x = u.first;
  105. 		int y = u.second;
  106.  
  107. 		for(auto& dir : dirs){
  108. 			int i = x + dir[0];
  109. 			int j = y + dir[1];
  110.  
  111. 			if(i<0 || i>=m || j<0 || j>=n ||  visited[i][j]) continue;
  112. 			q.push({i, j});
  113. 			visited[i][j] = true;
  114. 			lvl[i][j] = lvl[x][y] + 1;
  115.  
  116. 			//* Min Distance calculation
  117. 			if(a[i][j] == 1) mini = min(mini, lvl[i][j]);
  118. 		}
  119.  
  120. 	}
  121.  
  122.  
  123. 	//* Further Optimization : 
  124. 	//* Calculate mini directly above (not here)
  125.  
  126. 	// for(int i=0; i<m; i++){
  127. 	// 	for(int j=0; j<n; j++){
  128. 	// 		if( a[i][j] == 0 || a[i][j] == 2) continue;
  129. 	// 		mini = min(mini, lvl[i][j]);
  130. 	// 	}
  131. 	// }
  132.  
  133. 	cout << mini-1 << endl;
  134.  
  135. }
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146. void solve() {
  147.  
  148.     int m, n;
  149.     cin>>m >> n;
  150.     a.resize(m, vector<int>(n, 0));
  151.     for(int i=0; i<m; i++){
  152.     	for(int j=0; j<n; j++){
  153.     		cin >> a[i][j];
  154.     	}
  155.     }
  156.  
  157.     consistency(m, n);
  158.  
  159.  
  160. }
  161.  
  162.  
  163.  
  164.  
  165.  
  166. int32_t main() {
  167.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  168.  
  169.     int t = 1;
  170.     // cin >> t;
  171.     while (t--) {
  172.         solve();
  173.     }
  174.  
  175.     return 0;
  176. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
8 7
0 0 0 0 0 0 0 
0 1 1 1 0 0 0
0 1 0 1 0 0 0 
0 1 1 1 0 0 0 
0 0 0 0 0 1 1
0 0 0 0 1 1 1
0 0 0 0 0 1 0
0 0 0 0 0 0 0
stdout
copy 
2
https://ideone.com/F6heml
language:
C++14 (gcc 8.3)
created:
5 hours 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!