Dang_Quan_10_Tin

TOP HSGTPHCM L9 2016-2017

Jan 15th, 2022
692
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "TOP"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using ld = long double;
  11.  
  12. constexpr int N = 1e2 + 5;
  13. int n, m, h[N][N];
  14. int vis[N][N], mark; // Mảng đánh dấu
  15. bool OnTop[N][N];
  16.  
  17. void Read()
  18. {
  19.     cin >> n >> m;
  20.  
  21.     for (int i = 1; i <= n; ++i)
  22.         for (int j = 1; j <= m; ++j)
  23.             cin >> h[i][j];
  24. }
  25.  
  26. bool BFS(int x, int y) // Các ô có thể đến được từ ô (x, y) mà không cần "đi xuống"
  27. {
  28.     queue<pair<int, int>> q;
  29.     q.emplace(x, y);
  30.     ++mark; // Ta sử dụng kĩ thuật đánh dấu bằng số nguyên để tránh việc phải khởi tạo lại mảng đánh dấu
  31.  
  32.     vis[x][y] = mark;
  33.  
  34.     while (!q.empty())
  35.     {
  36.         pair<int, int> c = q.front();
  37.         q.pop();
  38.  
  39.         if (h[c.first][c.second] > h[x][y]) // Có thể "đi lên" ô cao hơn
  40.             return true;
  41.  
  42.         for (int i = -1; i <= 1; ++i)
  43.             for (int j = -1; j <= 1; ++j)
  44.             {
  45.                 int u = c.first + i,
  46.                     v = c.second + j;
  47.  
  48.                 if (u > 0 && u <= n && v > 0 && v <= m) // Ô này vẫn nằm trong đồn điền nhà Tý
  49.                     if (h[u][v] >= h[x][y] && vis[u][v] != mark)
  50.                     {
  51.                         vis[u][v] = mark;
  52.                         q.emplace(u, v);
  53.                     }
  54.             }
  55.     }
  56.  
  57.     return false;
  58. }
  59.  
  60. void Solve()
  61. {
  62.     for (int i = 1; i <= n; ++i)
  63.         for (int j = 1; j <= m; ++j)
  64.             OnTop[i][j] = !BFS(i, j); // Không thể đến được ô cao hơn mà không "đi xuống"
  65.  
  66.     int ans(0);
  67.  
  68.     for (int i = 1; i <= n; ++i)
  69.         for (int j = 1; j <= m; ++j)
  70.             if (OnTop[i][j])
  71.             {
  72.                 if (OnTop[i - 1][j - 1] || OnTop[i - 1][j] || OnTop[i - 1][j + 1] || OnTop[i][j - 1])
  73.                     ;
  74.                 else
  75.                     ++ans;
  76.             }
  77.  
  78.     cout << ans;
  79. }
  80.  
  81. int32_t main()
  82. {
  83.     ios::sync_with_stdio(0);
  84.     cin.tie(0);
  85.     cout.tie(0);
  86.     if (fopen(task ".INP", "r"))
  87.     {
  88.         freopen(task ".INP", "r", stdin);
  89.         freopen(task ".OUT", "w", stdout);
  90.     }
  91.  
  92.     Read();
  93.     Solve();
  94. }
  95.  
RAW Paste Data