[BOJ] 1987 알파벳

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

 

문제 풀이:

그냥 간단한 DFS 문제이다.`

 

TestCase:

2 4
CAAB
ADEM

=> 6

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <string.h>

using namespace std;

int n, m,res;
char arr[22][22];
bool visit[22][22],exist[26];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void func(int x, int y, int cnt=1) {
	for (int i = 0; i < 4; i++) {
		int curx = x + dx[i];
		int cury = y + dy[i];
		if (curx < 0 || curx >= n || cury < 0 || cury >= m||visit[curx][cury]) continue;
		if (exist[arr[curx][cury] - 'A']) continue;
		visit[curx][cury] = true;
		exist[arr[curx][cury] - 'A'] = true;
		func(curx, cury, cnt + 1);
		visit[curx][cury] = false;
		exist[arr[curx][cury] - 'A'] = false;
	}
	res = max(res, cnt);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	visit[0][0] = true;
	exist[arr[0][0] - 'A'] = true;
	func(0,0);
	
	cout << res << '\n';
	return 0;
}