[16929] Two Dots

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

16929번: Two Dots

<문제>

dfs로 탐색하다, depth가 4이상일때 시작한 위치를 만났으면 Yes.

모든 시작점에 대해 dfs를 호출해주면 된다.

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

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

int n, m, ey, ex;

char a[55][55];

bool vst[55][55];

void f(int cy, int cx, int cnt) {

    for (int i = 0; i < 4; i++) {

        int y = cy + dy[i];

        int x = cx + dx[i];

        if (y < 0 || x < 0 || y >= n || x >= m) continue;

        if (a[y][x] != a[ey][ex]) continue;

        if (y == ey && x == ex && cnt >= 4) {

            cout << "Yes";

            exit(0);

        }

        if (vst[y][x]) continue;

        vst[y][x] = true;

        f(y, x, cnt + 1);

    }

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n >> m;

    int i, j;

    for (i = 0; i < n; i++)

        for (j = 0; j < m; j++) cin >> a[i][j];

    for (i = 0; i < n; i++) {

        for (j = 0; j < m; j++) {

            memset(vst, 0, sizeof(vst));

            ey = i, ex = j;

            vst[ey][ex] = true;

            f(i, j, 1);

        }

    }

    cout << "No";

    return 0;

}