BaekJoon 1987 알파벳

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

소스 결과 : 1984KB 488ms

출처 : BackJoon, Croatian Highschool Competitions in Infomatics 2002 Regional Competition Jonior 

 

설명

DFS 문제

 

조건

1. 시작하는 칸도 포함 : 즉 최대값은 1부터 시작

2. 칸을 기준으로 중복 체크를 하는 것이 아닌 현재 칸의 알파벳을 밟은 적이 있는지를 검사

 

사용 입력 케이스

2 20  ABCDEFGHIJKLMNOPQRST  BCDEFGHIJKLMNOPQRSTU	21
3 3  ABC  DEF  GHI	9
4 4  AAAA  BAAA   CAAA  DEFG	7
2 2  AA  AA	1
20 2  AB  BC  CD  DE  EF  FG  GH  HI  IJ  JK  KL  LM  MN  NO  OP  PQ   QR  RS  ST  TU	21

 

소스코드

#include <iostream>
#include <string>

using namespace std;

int posX[4] = { 1, 0, -1, 0 };
int posY[4] = { 0, 1, 0 , -1 };
char map[20][20];
int row, col;
int mMax = 1;

void algo(int x, int y, int step, bool alpha[26]) {

	if (alpha[map[x][y] - 'A'])
	{
		if (step > mMax)
			mMax = step;
	}

	alpha[map[x][y] - 'A'] = true;

	for (int i = 0; i < 4; i++) // Right, Bottom, Left, Top
	{
		if (0 <= x + posX[i] && x + posX[i] < row && 0 <= y + posY[i] && y + posY[i] < col)
		{
			int idx = int(map[x + posX[i]][y + posY[i]]) - 'A';
			if (!alpha[idx])
			{
				alpha[idx] = true;
				algo(x + posX[i], y + posY[i], step + 1, alpha);
				alpha[idx] = false;
			}
		}
	}
}

int main()
{
	cin >> row >> col;

	cin.ignore();
	for (int i = 0; i < row; i++)
		cin >> map[i];

	bool alpha[26];
	fill_n(alpha, 26, false);

	algo(0, 0, 1, alpha);

	cout << mMax;

	return 0;
}