Derga

Untitled

Jun 19th, 2024
27
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.73 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <map>
  4. #include <string>
  5. #include <queue>
  6. #include <tuple>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. void Dfs(const vector<vector<char>>& go_field, vector<vector<bool>>& is_visited,
  12. int i, int j, int& empty_neighbor_cells_count)
  13. {
  14. is_visited[i][j] = true;
  15. if (go_field[i][j] == '.') {
  16. ++empty_neighbor_cells_count; return;
  17. }
  18.  
  19. for (int di = -1; di <= 1; ++di) {
  20. for (int dj = -1; dj <= 1; ++dj) {
  21. if (di * di + dj * dj != 1) continue;
  22.  
  23. int ni = i + di;
  24. int nj = j + dj;
  25.  
  26. if (ni < 0 || go_field.size() <= ni || nj < 0 || go_field.front().size() <= nj) continue;
  27. if (is_visited[ni][nj]) continue;
  28. if (go_field[ni][nj] == 'W') continue;
  29.  
  30. Dfs(go_field, is_visited, ni, nj, empty_neighbor_cells_count);
  31. }
  32. }
  33.  
  34.  
  35. }
  36.  
  37. int main() {
  38. int side_size;
  39. cin >> side_size;
  40.  
  41. vector<vector<char>> go_field(side_size, vector<char>(side_size));
  42. for (auto& row : go_field) {
  43. for (char& ch : row) {
  44. cin >> ch;
  45. }
  46. }
  47.  
  48. vector<vector<bool>> is_visited(side_size, vector<bool>(side_size, false));
  49. int cnt = 0;
  50. for (int i = 0; i < side_size; ++i) {
  51. for (int j = 0; j < side_size; ++j) {
  52. if (go_field[i][j] == '.' || go_field[i][j] == 'W') continue;
  53. if (is_visited[i][j]) continue;
  54.  
  55. int empty_neighbor_cells_count = 0;
  56. bool got_white_atroud = false;
  57. Dfs(go_field, is_visited, i, j, empty_neighbor_cells_count);
  58. if (empty_neighbor_cells_count == 1) ++cnt;
  59. }
  60. }
  61.  
  62. cout << cnt;
  63.  
  64. return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment