시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 15 2 2 16.667%

문제

블럭 퍼즐은 단위 정사각형으로 나누어져 있는 정사각형 그리드에서 즐기는 게임이다. 칸 중의 일부는 시작칸으로 표시되어 있고, 한 칸은 도착칸으로 표시되어 있다.

게임은 시작칸 중의 하나에 1×1×2 블럭을 놓으면서 시작한다. 이 때, 1×1면이 칸과 닿아야 한다. 게임의 목표는 블럭을 적절히 움직여서 도착칸에 서있게 만드는 것이다. 즉, 1×1면이 도착칸에 닿아있어야 한다.

게임은 블럭을 굴리면서 진행한다. 1×1면이 그리드에 닿아있는 경우에는 네 방향 모든 방향으로 블럭을 굴릴 수 있다. 하지만, 2×1 면이 그리드에 닿아있는 경우에는 1×1면이 그리드에 닿게만 굴릴 수 있다. 즉, 항상 변의 길이가 1인 곳을 기준으로 굴려야 한다.

아래 그림은 이동시킬 수 있는 방법을 모두 나타낸 것이고, 이전 상태가 반투명으로 그려져 있다.

이 게임이 어려워지는 이유는 일부 칸에 구멍이 뚫려있기 때문이다. 블럭의 바닥면이 모두 구멍 위에 있다면, 블럭은 구멍으로 떨어지고 게임에서 패배하게 된다. 만약, 블럭의 바닥면이 2×1이고, 구멍이 두 칸 중 하나에만 있다면 블럭은 떨어지지 않는다. 블럭은 게임판의 경계에 걸칠 수도 있다. 즉, 바닥면이 2x1인 경우에 한 칸이 게임판 위에 있고, 한 칸이 게임판 밖에 있는 경우는 가능하다.

홍준이는 이 게임을 너무 많이 했기 때문에 지루해졌다. 따라서, 이 게임을 풀 수 없게 하기 위해서 구멍을 만들어보려고 한다. 홍준이는 시작칸과 도착칸이 아닌 칸을 구멍으로 만들 수 있다. 

게임판의 상태가 주어졌을 때, 게임을 풀 수 없게 만들기 위해 홍준이가 바꿔야 하는 칸의 개수의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임판의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 상태가 주어진다. (3 ≤ N ≤ 50)

'.'은 칸, 'H'는 구멍, 'b'는 시작점, '$'는 도착점을 나타낸다.

게임판에 있는 '$'의 개수는 항상 1개이며, 'b'는 1개 이상이다.

출력

첫째 줄에 게임을 풀 수 없게 하기 위해서 구멍으로 바꿔야 하는 칸의 최소 개수를 출력한다. 만약, 게임을 풀 수 없게 할 수 없다면 -1을 출력한다.

예제 입력

4
b..$
....
HHHH
HHHH

예제 출력

2

예제 입력 2

15
............H..
...............
...............
HHH$HHH.....H..
HHHHHHH........
HHHHHHHH.......
......b..H.....
...............
...............
...H..H..H.....
...............
...............
...............
...............
...............

예제 출력 2

0

예제 입력 3

15
............H..
...............
...............
HHH$HHH........
HHHHHHH........
HHHHHHHH.......
......b..H.....
...............
...............
...H..H..H.....
...............
...............
...............
...............
...............

예제 출력 3

1

예제 입력 4

7
b..$...
...H...
.......
b..b..b
...H...
.......
b..b..b

예제 출력 4

4

예제 입력 5

7
b..b..b
..b..b.
.......
b..$bbb
.b.....
....b..
b..b..b

예제 출력 5

-1

힌트