35501번 - $2N$ 격자판

$2$행 $N$열 격자가 주어진다. 각 칸은 문자 S, X, O 중 하나로 나타난다. 각 문자의 의미는 다음과 같다.

• S: 시작 위치이며, 정확히 한 칸 존재한다. 해당 칸에는 착지할 수 없다.
• X: 반드시 한 번 방문해야 하는 칸이다.
• O: 장애물이다. 이 칸에는 착지할 수 없다.

플레이어는 매 턴 착지 가능한 임의의 칸으로 이동할 수 있다. $(r_1,c_1)$에서 $(r_2,c_2)$로 이동할 때, 이 이동에 드는 비용은 다음과 같다.

$cost\, =\,(|r_1-r_2|+|c_1-c_2|) -1$

S에서 시작하여 모든 X가 적힌 칸을 정확히 한 번씩 방문하는 경로들 중 총 비용의 최솟값을 구해보자.

첫 번째 줄에 격자의 열의 개수를 나타내는 정수 $N$이 주어진다.

두 번째 줄과 세 번째 줄에 길이 $N$의 문자열이 한 줄에 하나씩 주어진다. $i+1$번째 줄의 $j$번째 문자는 $i$행 $j$열 칸을 나타낸다.

첫 번째 줄에 총 비용의 최솟값을 출력한다.

• $1\le N\le 1\, 000$
• $1\le i\le 2$
• $1\le j\le N$
• X는 하나 이상 주어진다.
• S는 정확히 한 번 주어진다.
• 입력 문자열은 S, X, O 로만 이루어져 있다.