Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using i32 = int;
- using ui32 = unsigned int;
- using i64 = long long;
- using ui64 = unsigned long long;
- const ui32 MSIZE = 51;
- std::vector<std::pair<ui32, ui32>> g[MSIZE][MSIZE];
- char arr[MSIZE][MSIZE];
- i32 dx[4]{0, 0, -1, 1};
- i32 dy[4]{-1, 1, 0, 0};
- i32 color[MSIZE][MSIZE];
- bool Dfs(int x, int y, int px = -1, int py = -1) {
- color[x][y] = 1;
- for (const auto& [nx, ny] : g[x][y]) {
- if (nx == px && ny == py) continue;
- if (color[nx][ny] == 1) {
- return true;
- }
- if (color[nx][ny] == 0) {
- if (Dfs(nx, ny, x, y)) {
- return true;
- }
- }
- }
- color[x][y] = 2;
- return false;
- }
- i32 main() {
- ui32 n, m;
- scanf("%d%d", &n, &m);
- for (ui32 i = 0; i < n; i++) {
- scanf("%s", arr[i]);
- }
- for (ui32 i = 0; i < n; i++) {
- for (ui32 j = 0; j < m; j++) {
- for (i32 k = 0; k < 4; k++) {
- i32 x = i32(i) + dx[k];
- i32 y = i32(j) + dy[k];
- if (x < 0 or y < 0 or x >= i32(n) or y >= i32(m)) continue;
- if (arr[x][y] != arr[i][j]) continue;
- g[i][j].emplace_back(x, y);
- }
- }
- }
- bool cycleExists = false;
- for (ui32 i = 0; i < n; i++) {
- for (ui32 j = 0; j < m; j++) {
- if (color[i][j] == 0) {
- if (Dfs(i, j)) {
- cycleExists = true;
- }
- }
- }
- }
- puts(cycleExists ? "Yes" : "No");
- }
Add Comment
Please, Sign In to add comment