백준 1987 알파벳 c++

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

1987번: 알파벳

와이 시간초과??

#include <iostream> // 시간초과
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>

using namespace	std;
int col, row, res = -1;
vector<string> board;
unordered_set<char> s;
int dx[4] = {1, 0,-1 ,0};
int dy[4] = {0, -1, 0 ,1};

void dfs(int depth, int x, int y) {
	if (s.find(board[x][y]) != s.end()) {
		res = max(depth, res);
		return ;
	}
	s.insert(board[x][y]);
	for (int i = 0; i < 4; i++) {
		int newX = x + dx[i];
		int newY = y + dy[i];
		if (newX < 0 || newY < 0 || newX >= col || newY >= row)
			continue;
		dfs(depth + 1, newX, newY);
	}
	s.erase(board[x][y]);
}


int	main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin >> col >> row;

	for (int i = 0; i < col; i++) {
		string input;
		cin >> input;
		board.push_back(input);
	}
	dfs(0, 0, 0);
	cout << res;
}

unordered_set으로 O(1)에 가깝게 탐색해도 시간초과로 터진다. bool visit배열을 만들어서 해결했다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#include <unordered_set>
#include <cstring>

using namespace	std;
int col, row, res = -1;
vector<string> board;
bool visit[27];
int dx[4] = {1, 0,-1 ,0};
int dy[4] = {0, -1, 0 ,1};

void dfs(int depth, int x, int y) {
	if (visit[board[x][y] - 'A'] == true) {
		res = max(depth, res);
		return ;
	}
	visit[board[x][y] - 'A'] = true;
	for (int i = 0; i < 4; i++) {
		int newX = x + dx[i];
		int newY = y + dy[i];
		if (newX < 0 || newY < 0 || newX >= col || newY >= row)
			continue;
		dfs(depth + 1, newX, newY);
	}
	visit[board[x][y] - 'A'] = false;
}


int	main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin >> col >> row;
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < col; i++) {
		string input;
		cin >> input;
		board.push_back(input);
	}
    if (col == 1 && row == 1) { ////////////// 재채점 아놔
		cout << 1;
		return 0;
	}
	dfs(0, 0, 0);
	cout << res;
}

갑자기 재채점 됐대서 들어가 보니까 98프로에서 터지더라.

딱 봐도
1 1
A

이거같아서 예외케이스 처리 해 줬다.

어이업성