Advertisement
Derga

Untitled

Aug 24th, 2023 (edited)
832
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None | 0 0
  1. #include <climits>
  2. #include <cstdint>
  3. #include <iostream>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. int32_t GetCount(const vector< vector< int32_t > >& heights, vector< vector< bool > >& is_visited, int32_t x, int32_t y)
  9. {
  10.     int32_t cur_height = heights[x][y];
  11.     is_visited[x][y] = true;
  12.     for (int32_t dx = -1; dx <= 1; ++dx)
  13.     {
  14.         for (int32_t dy = -1; dy <= 1; ++dy)
  15.         {
  16.             if ((dx * dx + dy * dy) != 1)
  17.                 continue;
  18.  
  19.             int32_t nx = x + dx;
  20.             int32_t ny = y + dy;
  21.  
  22.             if (cur_height < heights[nx][ny])
  23.                 continue;
  24.  
  25.             if (cur_height > heights[nx][ny] && is_visited[nx][ny])
  26.             {
  27.                 return 0;
  28.             }
  29.  
  30.             if (is_visited[nx][ny])
  31.                 continue;
  32.  
  33.             return GetCount(heights, is_visited, nx, ny);
  34.         }
  35.     }
  36.  
  37.     return 1;
  38. }
  39.  
  40. int32_t GetTrapDoorsCount(const vector< vector< int > >& heights)
  41. {
  42.     int32_t trap_doors_count = 0;
  43.     vector< vector< bool > > is_visited(heights.size(), vector< bool >(heights.front().size(), false));
  44.  
  45.     for (int32_t i = 1; i < heights.size() - 1; ++i)
  46.     {
  47.         for (int32_t j = 1; j < heights.front().size() - 1; ++j)
  48.         {
  49.             if (is_visited[i][j])
  50.                 continue;
  51.  
  52.             trap_doors_count += GetCount(heights, is_visited, i, j);
  53.         }
  54.     }
  55.  
  56.     return trap_doors_count;
  57. }
  58.  
  59. int main()
  60. {
  61.     int32_t rows_count, columns_count;
  62.     cin >> rows_count >> columns_count;
  63.  
  64.     vector< vector< int32_t > > heights(rows_count + 2, vector< int >(columns_count + 2, INT32_MAX));
  65.     for (int32_t i = 1; i < heights.size() - 1; ++i)
  66.     {
  67.         for (int32_t j = 1; j < heights.front().size() - 1; ++j)
  68.         {
  69.             cin >> heights[i][j];
  70.         }
  71.     }
  72.  
  73.     cout << GetTrapDoorsCount(heights);
  74.  
  75.     return 0;
  76. }
  77.  
  78. /*
  79. test2
  80. 4 4
  81. 4 3 2 1
  82. 3 3 2 1
  83. 2 2 2 1
  84. 1 1 1 1
  85. answer 1
  86.  
  87. test3
  88. 4 4
  89. 4 3 2 1
  90. 3 3 2 2
  91. 2 2 2 1
  92. 1 2 1 2
  93. answer 4
  94.  
  95. test4
  96. 1 1
  97. 5
  98. answer 1
  99.  
  100. test5
  101. 4 4
  102. 1 1 1 1
  103. 1 1 1 1
  104. 1 1 1 1
  105. 1 1 1 1
  106. answer 1
  107.  
  108. test6
  109. 2 2
  110. 3 4
  111. 1 1
  112. answer 1
  113.  
  114. test7
  115. 2 3
  116. 1 2 2
  117. 2 3 3
  118. answer - 1
  119.  
  120. test8
  121. 5 6
  122. 2 1 2 3 2 1
  123. 2 1 3 2 3 1
  124. 2 1 1 2 1 1
  125. 1 1 1 1 1 2
  126. 1 2 1 3 1 2
  127. answer - 1
  128. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement