백준 1987 알파벳 // 노드가 각자의visit을 가져야한다면 원복! , dfs visit[now] [next]둘중 하나만 해라

1987번: 알파벳 (acmicpc.net)

1987번: 알파벳

* 노드가 각자의visit을 가져야한다면 원복! 

visited[a[ny][nx] - 'A'] = 1;
dfs(ny, nx, cnt + 1);
visited[a[ny][nx] - 'A'] = 0;

* dfs visit[now] [next]둘중 하나만 해라 

void dfs(int y, int x, int cnt)
{
	v[y][x]=1;	//항상 참이됨 
    
    ~~~~
    v[ny][nx]=1;
    dfs[ny][nx];
}

문제 : v[y][x]가 항상 참이됨.

 

* 문자 to 숫자

문자-'A'

#include <bits/stdc++.h> 
#define MAX 100000
#define y1 aaaaa

using namespace std;
int ret, cnt;
int n, m,  y1, x1, y2, x2, ny, nx,
dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
int visited[404];
char a[24][24];
queue<pair<int, int>> swanQ,waterQ,swanTemp,waterTemp;

bool in(int a, int b) {
	return 0 <= a && a < n && 0 <= b && b < m;
}
/*
* dfs
* now만 방문처리한건지, next만 할건지 결정하라.
* next만 방문처리하는 dfs
*/
void dfs(int y, int x, int cnt)
{
	ret = max(ret, cnt);
	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (!in(ny, nx)) continue;
		if (visited[a[ny][nx] - 'A']) continue;
		visited[a[ny][nx] - 'A'] = 1;
		dfs(ny, nx, cnt + 1);
		visited[a[ny][nx] - 'A'] = 0;
	}
	return;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	visited[a[0][0] - 'A'] = 1;
	dfs(0, 0, 1);
	cout << ret;

}
/*
5 17
 */