[백준1987]알파벳

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

1)문제분류

-DFS

-백트레킹

2)문제해결

-현재까지 이 알파벳을 쓴적이있는지 없는지를 체크하며 재귀를 탄다, 없다면, 재귀타고,말이 갈수 있는 거리인 최댓값을 갱신해 준다..

-기본 DFS,백트레킹 인 듯하다

#include<iostream>

#include<algorithm>

using namespace std;

int r, c;

char map[22][22];

int alpa[30];

int xrr[4] = { 0,0,1,-1 };

int yrr[4] = { 1,-1,0,0 };

int ans = 1;

void dfs(int x, int y, int cnt)

{

    

for (int i = 0; i < 4; i++)

{

int cx = x + xrr[i];

int cy = y + yrr[i];

if (cx<0 || cy<0 || cx>r - 1 || cy>c - 1)continue;

if (alpa[map[cx][cy] - 'A'] == false)

{

alpa[map[cx][cy] - 'A'] = true;

ans = max(cnt + 1, ans);

dfs(cx, cy, cnt + 1);

alpa[map[cx][cy] - 'A'] = false;

}

}

}

int main()

{

cin >> r >> c;

for (int i = 0; i < r; i++)

{

for (int j = 0; j < c; j++)

{

cin >> map[i][j];

}

}

alpa[map[0][0] - 'A'] = true;

dfs(0, 0, 1);

cout << ans << endl;

}