[1987] 알파벳

• 입력: 세로 r 가로 c r*c로 된 대문자 집합
• 출력: 상하좌우로 움직이면서 방문했던 알파벳은 방문하지 않았을 때 최대의 길이
• 알고리즘: DFS, 백트래킹
• 소스코드
?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <string> #include <cstdio> using namespace std;   void DFS(int, int, int, int&);   int r, c; vector<string> board; vector<bool> alphabet(26, false);   int main() {     scanf("%d%d", &r, &c);       board = vector<string>(r);     for (int i = 0; i < r; i++)         cin >> board[i];       int max = 0;       DFS(0, 0, 1, max);     printf("%d\n", max);       return 0; }   void DFS(int x, int y, int d, int& m) {     alphabet[board[x][y] - 'A'] = true;       if (m < d)         m = d;       if (x + 1 < r && !alphabet[board[x + 1][y] - 'A'])         DFS(x + 1, y, d + 1, m);     if (y + 1 < c && !alphabet[board[x][y + 1] - 'A'])         DFS(x, y + 1, d + 1, m);     if (x - 1 >= 0 && !alphabet[board[x - 1][y] - 'A'])         DFS(x - 1, y, d + 1, m);     if (y - 1 >= 0 && !alphabet[board[x][y - 1] - 'A'])         DFS(x, y - 1, d + 1, m);       alphabet[board[x][y] - 'A'] = false; }

• 문제 참고: https://www.acmicpc.net/problem/1987