Coding Test - cpp/DFS
[백준 1987: 알파벳] - C++
에드윈H
2021. 2. 15. 12:58
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
#include<iostream>
#include<string>
using namespace std;
int r, c;
char map[20][20];
bool check[26];
int result = 0;
int dir[4][2] = {
{-1,0}
,{0,1}
,{1,0}
,{0,-1}
};
void D(int _x, int _y, int cnt)
{
if (result < cnt)
result = cnt;
for (int i = 0; i < 4; i++)
{
int nextX = _x + dir[i][0];
int nextY = _y + dir[i][1];
if (nextX < 0 || nextY < 0 || r <= nextX || c <= nextY)
continue;
int num = map[nextX][nextY] - '0';
if (check[num] == false)
{
check[num] = true;
D(nextX, nextY, cnt + 1);
check[num] = false;
}
}
}
int main() {
string n;
cin >> r >> c;
for (int i = 0; i < r; i++)
{
cin >> n;
for (int j = 0; j < c; j++)
{
map[i][j] = n[j];
}
}
check[map[0][0] - '0'] = true;
D(0, 0, 1);
cout << result << endl;
return 0;
}