장애물 코스

$1 \times 1$ 크기의 타일로 이루어진 $N \times N$ ($1 \le N \le 100$) 크기의 정사각형 밭이 있다. 일부 타일은 소가 지나갈 수 없으며 x로 표시된다. 아래는 $5 \times 5$ 크기의 밭 예시이다.

. . B x .
. x x A .
. . . x .
. x . . .
. . x . .

소 베시는 A로 표시된 타일에서 출발하여, 소금을 핥기 위해 B로 표시된 타일로 이동하려고 한다. 소는 방향을 트는 것을 싫어하며, 밭의 변과 평행하게(위·아래·왼쪽·오른쪽으로) 한 번에 한 칸씩만 이동할 수 있다. 베시는 출발할 때와 도착할 때 어느 방향을 향하고 있어도 상관없다. A에서 B로 가는 모든 경로 중, $90$도 회전 횟수의 최솟값을 구하여라. B는 A에서 반드시 도달할 수 있음이 보장된다.

• 첫째 줄: 정수 $N$.
• $2$째 줄부터 $N+1$째 줄까지: $i+1$째 줄은 밭의 $i$번째 행을 나타내며, ., x, A, B 중 하나인 문자 $N$개로 이루어지고 공백은 없다.

• 첫째 줄: A에서 B로 가는 경로에서 필요한 $90$도 회전 횟수의 최솟값(정수 하나).

첫 번째 예제에서 소는 최소 $2$번 회전해야 한다. 예를 들어, 남쪽을 향해 남쪽으로 한 칸 이동하고, 서쪽으로 방향을 튼 뒤 서쪽으로 두 칸 이동한 다음, 다시 남쪽으로 방향을 틀어 B로 한 칸 이동하면 된다.