시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

연결된, 무향 그래프 G=(V, E)가 주어졌을 때, V가 정점의 집합을 나타내고, E가 간선의 집합을 나타낸다고 하자. V의 부분집합 S를 G에서 제거했을 때, 그래프가 두 개의 연결 요소로 나눠지면 S를 분리자라고 한다. 그래프에서 정점을 제거하면 제거한 정점에 연결된 간선도 함께 제거된다. 이와 같은 상황을 [S, W, B] 라는 기호로 나타내기로 하자. 이는 그래프가 분리자 S에 의해서 W와 B라는 두 개의 연결 요소로 나뉘어 진다는 의미이다.

우리는 격자 모양의 그래프에서의 분리자를 살펴보려 한다. 이 그래프에서 각각의 격자점이 정점을 이루며, 각각의 정점은 이웃한 8개의 정점들과 연결되어 있다. 아래에 6×6 격자 에 대한 예제 그림이 있다. 흰색은 W, 회색은 S, 검은색은 B를 나타낸다.

문제를 단순화하기 위해, 다음의 조건을 만족하는 분리자만 다루기로 하자.

  1. 분리자의 부분집합은 분리자를 이루지 않는다.
  2. 분리자는 그래프에서 맨 윗줄의 한 점과 맨 아랫줄의 한 점을 포함한다. 단, 0, 5, 30, 35는 제외한다.
  3. 분리자를 따라서 그래프를 위에서 아래로 이동할 때, 내려오다가 다시 올라가는 경우는 없다.

이제 다음의 두 단계를 수행하여 분리자의 크기를 줄이려고 한다.

  1. B에서 몇 개의 정점을 택해서 S에 포함시킨다. 이 때 택한 정점들은 반드시 왼쪽 정점으로 S에 포함된 정점을 가지고 있어야 한다.
  2. S에서 몇 개의 정점을 제거하여 W에 포함시킨다. 단, 이전 단계에서 포함시킨 정점들은 제거할 수 없다.

이와 같은 개선 방법을 이용하여 S가 여전히 분리자이도록 하고, 이 때 S의 크기를 최소로 하라. 위의 예제는 다음과 같이 하면 S의 크기가 7로 최소가 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

첫째 줄에 격자의 크기를 나타내는 두 정수 N, M(3≤N,M≤200)이 주어진다. 이는 격자의 크기가 N×M이라는 의미이다. 다음 N개의 줄에는 M개의 문자가 주어지는데, 각각은 S, W, B 중의 하나이다. 이는 해당 정점이 S, W, B 중 어느 집합에 속해있는지를 나타낸다. W는 반드시 S의 왼쪽에 존재한다. 잘못된 입력이 주어지지는 않는다고 가정해도 좋다. 모든 문자는 붙어서 입력된다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

첫째 줄에 S의 최소 크기를 출력한다.

예제 입력

6 6
WWSBBB
WSSBBB
WSBBBB
WSBBBB
WSSSBB
WWWSBB
0 0

예제 출력

7

힌트