999ms

A. Лиса и две точки

Apr 8th, 2020
255
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using i32 = int;
  4. using ui32 = unsigned int;
  5. using i64 = long long;
  6. using ui64 = unsigned long long;
  7.  
  8. const ui32 MSIZE = 51;
  9.  
  10. std::vector<std::pair<ui32, ui32>> g[MSIZE][MSIZE];
  11. char arr[MSIZE][MSIZE];
  12.  
  13. i32 dx[4]{0, 0, -1, 1};
  14. i32 dy[4]{-1, 1, 0, 0};
  15.  
  16. i32 color[MSIZE][MSIZE];
  17.  
  18. bool Dfs(int x, int y, int px = -1, int py = -1) {
  19.   color[x][y] = 1;
  20.   for (const auto& [nx, ny] : g[x][y]) {
  21.     if (nx == px && ny == py) continue;
  22.     if (color[nx][ny] == 1) {
  23.       return true;
  24.     }
  25.     if (color[nx][ny] == 0) {
  26.       if (Dfs(nx, ny, x, y)) {
  27.         return true;
  28.       }
  29.     }
  30.   }
  31.   color[x][y] = 2;
  32.   return false;
  33. }
  34.  
  35. i32 main() {
  36.   ui32 n, m;
  37.   scanf("%d%d", &n, &m);
  38.   for (ui32 i = 0; i < n; i++) {
  39.     scanf("%s", arr[i]);
  40.   }
  41.  
  42.   for (ui32 i = 0; i < n; i++) {
  43.     for (ui32 j = 0; j < m; j++) {
  44.       for (i32 k = 0; k < 4; k++) {
  45.         i32 x = i32(i) + dx[k];
  46.         i32 y = i32(j) + dy[k];
  47.         if (x < 0 or y < 0 or x >= i32(n) or y >= i32(m)) continue;
  48.         if (arr[x][y] != arr[i][j]) continue;
  49.         g[i][j].emplace_back(x, y);
  50.       }
  51.     }
  52.   }
  53.   bool cycleExists = false;
  54.   for (ui32 i = 0; i < n; i++) {
  55.     for (ui32 j = 0; j < m; j++) {
  56.       if (color[i][j] == 0) {
  57.         if (Dfs(i, j)) {
  58.           cycleExists = true;
  59.         }
  60.       }
  61.     }
  62.   }
  63.   puts(cycleExists ? "Yes" : "No");
  64. }
Add Comment
Please, Sign In to add comment