BOJ 16929 Two Dots

https://www.acmicpc.net/problem/16929

16929번: Two Dots

 

여러 알파벳으로 이루어진 2차원 격자가 주어졌을 때, 해당 격자에서 같은 알파벳으로 이루어진 길이 4 이상의 사이클이 존재하는지 판단하는 문제입니다. dfs로 cycle을 찾듯이 풀면 되는데, 한 번 방문한 점은 시작 지점이 아닌 이상 다시 방문하지 않도록 해야 합니다.

 

이를 구현하기 위해 시작 위치와 현재 위치, 그리고 몇 개의 점을 지났는지 기록하고 4개 이상의 점을 지났고 시작 위치를 다시 방문했을 경우 true를 리턴하도록 하였습니다. 정점을 방문하기 직전에 visited를 1로 만들어주고, 정점을 방문하고 나서 다시 visited를 0으로 초기화하면 한 경로 내에서 방문했던 점은 다시 방문하지 않도록 구현할 수 있습니다.

 

$No$를 $NO$라고 써서 한 번 틀렸습니다...

 

아래는 코드입니다.

 

#include <bits/stdc++.h>

#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

const int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, -1, 1, 1, -1, 1, -1};

bool inrange(int i, int j, int n, int m) { return 0 <= i && i < n && 0 <= j && j < m; }

using namespace std;

int T, n, m, graph[55][55], visited[55][55];

int dfs(int sx, int sy, int x, int y, int cnt) {
    int ret = 0;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (!inrange(nx, ny, n, m)) continue;

        if (graph[nx][ny] != graph[x][y]) continue;

        if (visited[nx][ny]) {
            if (sx == nx && sy == ny && cnt >= 4) return 1;
            continue;
        }

        visited[nx][ny] = 1;
        if (dfs(sx, sy, nx, ny, cnt + 1)) ret = 1;
        visited[n][ny] = 0;
    }
    return ret;
}

int32_t main(void) {
    FastIO;

#ifdef HN
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    T = 1;
    //cin >> T;

    while (T--) {
        cin >> n >> m;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char c;
                cin >> c;
                graph[i][j] = c;
            }
        }

        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited[i][j] = 1;
                if (dfs(i, j, i, j, 1)) ans = 1;
                memset(visited, 0, sizeof(visited));
            }
        }

        if (ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}