fork download
copy 
  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 = 7e2 + 5;
  12. const int M = 7e2 + 5;  
  13.  
  14. /* trái - phải - lên - xuống - chéo lên trái - chéo lên phải - chéo xuống trái - chéo xuống phải */ 
  15. int dx[8] = {0, 0, -1, 1, -1, -1, 1, 1}; 
  16. int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};  
  17.  
  18. int n, m; 
  19. int h[N][M]; 
  20.  
  21. bool vis[N][M];  
  22.  
  23. bool ok(int x, int y) {
  24. 	return (1 <= x && x <= n && 1 <= y && y <= m);  
  25. }
  26.  
  27. void bfs(int sx, int sy, bool& is_top) {
  28. 	queue<ii> q;
  29.  
  30. 	vis[sx][sy] = true;  
  31. 	q.push({sx, sy});  
  32.  
  33. 	while (!q.empty()) {
  34. 		ii u = q.front(); q.pop();   
  35. 		int x = u.first, y = u.second;  
  36.  
  37. 		for (int i = 0; i < 8; i++) {
  38. 			int nx = x + dx[i], ny = y + dy[i]; 
  39.  
  40. 			if (ok(nx, ny)) {
  41. 				if (h[nx][ny] == h[x][y]) {
  42. 					if (!vis[nx][ny]) {
  43. 						vis[nx][ny] = true;  
  44. 						q.push({nx, ny});  
  45. 					}
  46. 				}
  47. 				else {
  48. 					is_top &= (h[nx][ny] < h[x][y]);   
  49. 				}
  50. 			}
  51. 		}
  52. 	} 	
  53. }
  54.  
  55. int main() {
  56. 	ios::sync_with_stdio(false); 
  57. 	cin.tie(nullptr); 	
  58. 	cin >> n >> m; 
  59. 	for (int x = 1; x <= n; x++) {
  60. 		for (int y = 1; y <= m; y++) cin >> h[x][y]; 
  61. 	}
  62.  
  63. 	int ans = 0;   
  64. 	for (int x = 1; x <= n; x++) {
  65. 		for (int y = 1; y <= m; y++) {
  66. 			if (!vis[x][y]) {
  67. 				bool is_top = true; // ô (x, y) có phải đỉnh đồi hay không
  68. 				bfs(x, y, is_top); 
  69. 				ans += is_top;   
  70. 			}
  71. 		}
  72. 	}
  73.  
  74. 	cout << ans << '\n'; 
  75. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
stdout
copy 
3
https://ideone.com/ZEl5nM
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!