fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e2 + 5; 
  12.  
  13. int dx[4] = {0, 0, -1, 1};  
  14. int dy[4] = {-1, 1, 0, 0};  
  15.  
  16. int n;   
  17. int h[N][N];   
  18.  
  19. bool vis[N][N]; 
  20.  
  21. bool ok(int x, int y) {
  22. 	return (1 <= x && x <= n && 1 <= y && y <= n && !vis[x][y]); 
  23. }
  24.  
  25. // Có tồn tại đường đi từ ô (sx, sy) đến ô (n, n) sao cho
  26. // chỉ đi qua các ô có giá trị nằm trong đoạn [lo, hi]
  27. bool bfs(int sx, int sy, int lo, int hi) {
  28. 	if (!(lo <= h[sx][sy] && h[sx][sy] <= hi)) return false;    
  29.  
  30. 	for (int x = 1; x <= n; x++) {
  31. 		for (int y = 1; y <= n; y++) vis[x][y] = false;  
  32. 	}
  33.  
  34. 	queue<ii> q;  
  35.  
  36. 	vis[sx][sy] = true;   
  37. 	q.push({sx, sy});  
  38.  
  39. 	while (!q.empty()) {
  40. 		ii u = q.front(); q.pop();  
  41. 		int x = u.first, y = u.second; 
  42.  
  43. 		if (x == n && y == n) return true;  
  44.  
  45. 		for (int i = 0; i < 4; i++) {
  46. 			int nx = x + dx[i], ny = y + dy[i];  
  47.  
  48. 			if (ok(nx, ny) && lo <= h[nx][ny] && h[nx][ny] <= hi) {
  49. 				vis[nx][ny] = true;  
  50. 				q.push({nx, ny});    
  51. 			}
  52. 		}	
  53. 	}
  54.  
  55. 	return false; 
  56. }
  57.  
  58. bool check(int mid) {
  59. 	for (int lo = 0; lo <= 110; lo++) {
  60. 		if (bfs(1, 1, lo, lo + mid)) return true; 
  61. 	}
  62. 	return false; 
  63. }
  64.  
  65. int main() {
  66. 	ios::sync_with_stdio(false); 
  67. 	cin.tie(nullptr); 	
  68. 	cin >> n;  
  69. 	for (int x = 1; x <= n; x++) {
  70. 		for (int y = 1; y <= n; y++) cin >> h[x][y]; 
  71. 	}
  72.  
  73. 	int l = 0, r = 110, ans = -1; 
  74. 	while (l <= r) {
  75. 		int mid = (l + r) >> 1; // chênh lệch giữa điểm cao nhất và thấp nhất
  76.  
  77. 		if (check(mid)) {
  78. 			ans = mid;  
  79. 			r = mid - 1; 
  80. 		}
  81. 		else {
  82. 			l = mid + 1; 
  83. 		}
  84. 	}
  85.  
  86. 	cout << ans << '\n'; 
  87. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
stdout 
2
https://ideone.com/79mZKJ
language:
C++14 (gcc 8.3)
created:
319 days 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!