(c++)백준 1987번: 알파벳

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

1987번: 알파벳

[풀이]

같은 알파벳이 적힌 칸을 두 번 지날 수 없다는 조건이 있으므로 새로운 알파벳을 지날 때마다 체크를 해주었다.

한 칸씩 움직일 때마다 최대 칸 수를 갱신한다.

 

#include <iostream>
#include <string>
using namespace std;

int R, C;
char Board[20][20];
bool check[25];//ascii코드로 변환해서 체크
const int dx[] = { -1,1,0,0 };//상,하
const int dy[] = { 0,0,-1,1 };//좌,우
int Max = 1;

void getStep(int cnt, int x, int y) {
	if (cnt > Max)Max = cnt;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= R || ny < 0 || ny >= C)
			continue;
		if (check[Board[nx][ny] - 'A'] == true)
			continue;
		check[Board[nx][ny] - 'A'] = true;
		getStep(cnt + 1, nx, ny);
		check[Board[nx][ny] - 'A'] = false;
	}
}

int main() {
	cin >> R >> C;
	string line;
	for (int i = 0; i < R; i++) {
		cin >> line;
		for (int j = 0; j < C; j++) {
			Board[i][j] = line[j];
		}
	}
	check[Board[0][0] - 'A'] = true;
	getStep(1, 0, 0);
	cout << Max << '\n';
	return 0;
}