PKU 1154 LETTERS

• 最悪ケースは下記のようなものだと思う

ABCDEFGHIJKLMNOPQRST
BCDEFGHIJKLMNOPQRSTU
CDEFGHIJKLMNOPQRSTUV
DEFGHIJKLMNOPQRSTUVW
FGHIJKLMNOPQRSTUVWXY
GHIJKLMNOPQRSTUVWXYZ
HIJKLMNOPQRSTUVWXYZZ
...

• 2^26なので全探索しても通るはず

static const int dx[] = {0, 0, 1, -1};
static const int dy[] = {1, -1, 0, 0};

int height, width;
char maze[32][32];
int answer = -1;
bool visited[0x100];

void dfs(int x, int y, int depth) {
	if (visited[maze[x][y]]) {
		return;
	}
	visited[maze[x][y]] = true;

	answer = max(answer, depth);

	for (int dir = 0; dir < 4; ++dir) {
		dfs(x + dx[dir], y + dy[dir], depth + 1);
	}

	visited[maze[x][y]] = false;
}

int main() {
	cin >> height >> width;
	memset(maze, 0, sizeof(maze));
	memset(visited, 0, sizeof(visited));
	visited[0] = true;
	for (int y = 1; y <= height; ++y) {
		for (int x = 1; x <= width; ++x) {
			cin >> maze[x][y];
		}
	}

	dfs(1, 1, 1);

	cout << answer << endl;
}