밟은 알파벳은 다시는 못밟고 최대한 깊숙이 들어갈 때 그 깊이 값을 구하는 문제이다.
본인은 DFS로 품.
이전에 풀었던 문제인데 DFS말고 다른 방법이 생각이 안나서 다시 DFS로 풀었는데
이 문제는 DFS + 비트 마스킹으로 visited와같은 배열을 관리하지 않고 풀 수가 있었다.
'&' 연산자로 방문했는지 안했는지를 확인하고
| 연산자로 방문처리를 한뒤 방문한 값을 인자로 넘기는 식이다.
#include <iostream>
using namespace std;
#define endl "\n"
int r, c, ret, ny, nx;
char arr[21][21];
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
bool Cango(int y, int x)
{
if (y < 0 || x < 0 || y >= r || x >= c) return false;
return true;
}
void Go(int y, int x, int num, int cnt)
{
ret = max(ret, cnt);
for (int i = 0; i < 4; ++i)
{
ny = y + dy[i]; nx = x + dx[i];
if (Cango(ny, nx) == false) continue;
int _next = (1 << int(arr[ny][nx] - 'A'));
// & 연산으로 방문했는지 안했는지 확인
if ((num & _next) == 0)
{
// 방문하지 않았다면 or 연산자로 방문처리.
Go(ny, nx, num | _next, cnt + 1);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ret = -1;
cin >> r >> c;
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
cin >> arr[i][j];
Go(0, 0, 1 << (int)(arr[0][0] - 'A'), 1);
cout << ret << endl;
return 0;
}