1987 알파벳

백트래킹 문제다.

<코드>

#include <string>
#include <algorithm>
#include <stdio.h>
 
using namespace std;
 
int r, c, dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
char a[20][22];
bool ch[26];
 
int dfs(int x, int y) {
    int ans = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c || ch[a[nx][ny] - 'A']) continue;
        ch[a[nx][ny] - 'A'] = 1;
        ans = max(ans, dfs(nx, ny) + 1);
        ch[a[nx][ny] - 'A'] = 0;
    }
    return ans;
}
 
int main() {
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; i++) scanf(" %s", &a[i]);
    ch[a[0][0] - 'A'] = 1;
    printf("%d\n",dfs(0, 0));
    return 0;
}