이문제 시간복잡도를 보면 좀 아리송? 하다.
일단 아리송해도 완탐밖에 답이 없으면 완탐을 진행을 해준다.
문제는 쉬운편이였던거 같다.
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 21
const int INF = 987654321;
int r, c, visited[MAX][MAX], dy[4] = { 0, 1, 0, -1 }, dx[4] = { -1, 0, 1, 0 }, ret = -1 * INF;
char arr[MAX][MAX];
int abc[30];
bool Cango(int y, int x)
{
if (y < 0 || y >= r || x < 0 || x >= c) return false;
return true;
}
char GetA(int y, int x)
{
char c = arr[y][x];
return c;
}
bool CheckA(int y, int x)
{
char c = arr[y][x];
int v = abc[int(c) - 65];
if (v == 0)
return true;
else
return false;
}
void Go(int y, int x)
{
if (ret < visited[y][x])
{
ret = visited[y][x];
}
for (int i = 0; i < 4; ++i)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (!Cango(ny, nx)) continue;
if (visited[ny][nx] || CheckA(ny, nx) == false) continue;
visited[ny][nx] = visited[y][x] + 1;
abc[int(GetA(ny, nx)) - 65] = 1;
Go(ny, nx);
visited[ny][nx] = 0;
abc[int(GetA(ny, nx)) - 65] = 0;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> r >> c;
for (int y = 0; y < r; ++y)
{
for (int x = 0; x < c; ++x)
{
cin >> arr[y][x];
}
}
visited[0][0] = 1;
abc[int(GetA(0, 0)) - 65] = 1;
Go(0, 0);
cout << ret << endl;
int a = 10;
return 0;
}