20497번 - Bessie's Revolution

Bessie는 John's Farm의 우민(牛民)이자 혁명 전사이다. 본래 John's Farm의 터는 Bessie와 소들이 평화롭게 풀을 뜯던 초원이었으나, John이 자본을 앞세워 불도저를 밀고 들어와 Farm을 차리면서 모든 것이 달라졌다.

그리하여 이 언덕들

따사로운 하늘

이 나무들의 윤곽이

지금까지 우리가 부여해왔던 허망한 의미를 단숨에 잃어버리고서

이제부터는 잃어버린 낙원보다도 더 먼 존재로 변해버리는 것이다.

Bessie는 Amy와 John이 있는 주방을 습격하고, 농장을 탈환하려고 한다.

Bessie와 참모진들은 주방의 지도를 입수했다. Bessie는 주방에 기습 병력을 배치하여 Amy와 John을 포위할 계획이다. Bessie는 John's Farm의 최고 전사인 당신을 투입하기로 했다. 당신의 임무는 주방의 한 격자에 장애물로 위장해 잠복하는 것이다. 당신이 잠복함으로 인해, 잠복한 격자가 속한 공간이 두 개 이상의 공간으로 분리되고, 그 공간들 사이의 이동이 불가능해져야 한다. 다시 말해, 잠복한 칸을 거치면 서로 이동할 수 있지만, 잠복한 칸을 거치지 않으면 서로 이동할 수 없는 두 격자가 존재해야 한다. 격자 간의 이동은 상하좌우 이동 $(r+1,c), (r-1,c), (r,c+1), (r,c-1)$이다. 물론, 격자 밖으로의 이동은 불가능하며 씽크대 또는 장애물이 존재하는 격자에는 잠복할 수 없다.

첫 번째 줄에 격자의 크기 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 $N \times N$ 크기의 주방의 평면도가 주어진다.

문제에서 제시한 조건에 맞게 잠복할 수 있는 격자의 개수를 출력한다.

• $1 \le N \le 11$
• 모든 격자 $A_{r,c}$ ($1 \le r,c \le N$)는 씽크대 'S' 또는 빈 격자 '.' 또는 장애물 '@'로 구성되어 있다.
• 'S'는 반드시 하나 주어진다.
• 'S'도 장애물로 취급한다.