더 어려운 소코반 문제

$N \times N$ 크기의 직사각형 격자에서 진행하는 소코반 게임이다. 각 칸은 빈 칸(., ASCII 46)이거나 벽(#, ASCII 35)이다. 또한 목적지 칸이 정확히 하나 있으며 *(ASCII 42)로 표시된다.

빈 칸 중 한 칸에는 플레이어가, 다른 한 칸에는 상자가 놓여 있다. 플레이어는 상하좌우로 인접한 빈 칸으로 한 칸씩 이동할 수 있다. 플레이어가 이동하려는 칸에 상자가 있으면, 그 상자는 같은 방향으로 한 칸 밀려난다. 단, 상자가 밀려나는 칸은 반드시 빈 칸이어야 한다(벽이거나 격자 밖이면 그 방향으로는 밀 수 없다).

소코반의 잘 알려진 목표는 상자를 목적지 칸으로 옮기는 것이며, 이때 이동 횟수를 최소로 한다. 한 번의 이동이란 플레이어가 한 칸 움직이는 것을 뜻하고, 그 이동이 상자를 미는 경우도 한 번으로 센다.

이 문제에서 풀어야 하는 것은 그 반대이다. 격자가 주어졌을 때, 플레이어와 상자의 시작 위치를 직접 골라서, 상자를 목적지로 옮기는 데 필요한 최소 이동 횟수가 최대가 되도록 하라. 그 최댓값을 출력한다.

상자를 목적지로 옮길 수 없는 배치는 고려하지 않는다. 상자를 처음부터 목적지 칸에 놓으면 이동이 0번 필요하므로, 답은 항상 0 이상이다.

첫째 줄에 격자의 크기 $N$이 주어진다. 이어지는 $N$개의 줄에는 각각 $N$개의 문자가 주어지며, 격자를 나타낸다. 입력 격자에는 목적지 칸과 인접한 빈 칸이 항상 하나 이상 존재한다.

상자를 목적지로 옮기는 데 필요한 최소 이동 횟수의 최댓값을 정수 하나로 출력한다.

• $2 \le N \le 25$