1987번: 알파벳

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


$O(4^w)$ // w는 min(26,r*c)

dfs 탐색을 이용해서 모든 경로를 조사한다.

#include<cstdio>
const int fx[] = { 0,0,1,-1 }, fy[] = { 1,-1,0,0 };
int ck[99], n, m, r;
char s[20][20];
void f(int x, int y, int z) {
    if (x < 0 || y < 0 || x >= n || y >= m || ck[s[x][y]]) return;
    r = r>z ? r : z;
    ck[s[x][y]] = 1;
    for (int i = 0; i < 4; i++) f(x + fx[i], y + fy[i], z + 1);
    ck[s[x][y]] = 0;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    f(0, 0, 1);
    printf("%d", r);
    return 0;
}