Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <climits>
- #include <cstdint>
- #include <iostream>
- #include <vector>
- using namespace std;
- int32_t GetCount(const vector< vector< int32_t > >& heights, vector< vector< bool > >& is_visited, int32_t x, int32_t y)
- {
- int32_t cur_height = heights[x][y];
- is_visited[x][y] = true;
- for (int32_t dx = -1; dx <= 1; ++dx)
- {
- for (int32_t dy = -1; dy <= 1; ++dy)
- {
- if ((dx * dx + dy * dy) != 1)
- continue;
- int32_t nx = x + dx;
- int32_t ny = y + dy;
- if (cur_height < heights[nx][ny])
- continue;
- if (cur_height > heights[nx][ny] && is_visited[nx][ny])
- {
- return 0;
- }
- if (is_visited[nx][ny])
- continue;
- return GetCount(heights, is_visited, nx, ny);
- }
- }
- return 1;
- }
- int32_t GetTrapDoorsCount(const vector< vector< int > >& heights)
- {
- int32_t trap_doors_count = 0;
- vector< vector< bool > > is_visited(heights.size(), vector< bool >(heights.front().size(), false));
- for (int32_t i = 1; i < heights.size() - 1; ++i)
- {
- for (int32_t j = 1; j < heights.front().size() - 1; ++j)
- {
- if (is_visited[i][j])
- continue;
- trap_doors_count += GetCount(heights, is_visited, i, j);
- }
- }
- return trap_doors_count;
- }
- int main()
- {
- int32_t rows_count, columns_count;
- cin >> rows_count >> columns_count;
- vector< vector< int32_t > > heights(rows_count + 2, vector< int >(columns_count + 2, INT32_MAX));
- for (int32_t i = 1; i < heights.size() - 1; ++i)
- {
- for (int32_t j = 1; j < heights.front().size() - 1; ++j)
- {
- cin >> heights[i][j];
- }
- }
- cout << GetTrapDoorsCount(heights);
- return 0;
- }
- /*
- test2
- 4 4
- 4 3 2 1
- 3 3 2 1
- 2 2 2 1
- 1 1 1 1
- answer 1
- test3
- 4 4
- 4 3 2 1
- 3 3 2 2
- 2 2 2 1
- 1 2 1 2
- answer 4
- test4
- 1 1
- 5
- answer 1
- test5
- 4 4
- 1 1 1 1
- 1 1 1 1
- 1 1 1 1
- 1 1 1 1
- answer 1
- test6
- 2 2
- 3 4
- 1 1
- answer 1
- test7
- 2 3
- 1 2 2
- 2 3 3
- answer - 1
- test8
- 5 6
- 2 1 2 3 2 1
- 2 1 3 2 3 1
- 2 1 1 2 1 1
- 1 1 1 1 1 2
- 1 2 1 3 1 2
- answer - 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement