초콜릿 칩 쿠키 만들기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

격자에 놓인 쿠키 모양이 주어질 때, 모든 쿠키 칸을 칩으로 만드는 데 필요한 최소 노출 횟수를 구합니다.

난이도: 보통10점 중 5점
유형: BFS, 행렬
정답자: 아직 제출이 없습니다

문제

단위 정사각형으로 이루어진 직사각형 팬을 갖춘 기계로 초콜릿 칩 쿠키를 만든다. 쿠키의 모양은 이미 정해져 있으며, 그 모양은 팬의 일부 칸을 차지한다. 쿠키의 모든 칸은 초콜릿 칩화되어야 한다.

쿠키를 만들려면 다음 두 단계를 반복한다.

단위 칸 몇 개에 쿠키 반죽을 놓는다.
쿠키 반죽을 묽은 초콜릿 칩 용액에 노출한다. 상하좌우 네 인접 칸이 모두 쿠키 반죽으로 채워지지 않은 쿠키 반죽 칸은 초콜릿 칩화된다. 팬의 가장자리에 있는 칸의 쿠키 반죽은 항상 칩화된다.

다음 예시는 왼쪽의 쿠키 모양 (s)를 만드는 방법을 보여 준다.

    (s)      (a1)     (a2)     (b1)     (b2) 
    -X-X-    -D-D-    -C-C-    -C-C-    -C-C-
    XXXXX    -D-D-    -C-C-    DCDCD    CCCCC
    XXXXX    -DDD-    -CCC-    DCCCD    CCCCC
    -XXX-    --D--    --C--    -DCD-    -CCC-
    --X--    -----    -----    --D--    --C--

먼저 쿠키 반죽을 8칸에 놓는다(a1). 첫 번째 용액 노출 후 모든 칸이 칩화된다(a2). 쿠키 반죽을 8칸 더 놓는다(b1). 두 번째 노출로 모든 칸이 칩화되어 쿠키가 완성된다(b2).

초콜릿 칩 용액은 비싸므로 노출 횟수를 가능한 한 적게 하려고 한다. 쿠키 모양이 주어졌을 때, 쿠키를 만드는 데 필요한 초콜릿 칩 용액 노출의 최소 횟수를 구한다.

입력

첫 줄에 두 정수 $n$ 과 $m$ ( $1 \leq n, m \leq 1\,000$ )이 주어진다. 이는 팬의 행 수와 열 수이다.

이어지는 $n$ 개의 줄에는 각각 정확히 $m$ 개의 문자로 이루어진 문자열이 주어진다. 문자 X는 쿠키가 차지한 칸을, -는 빈 칸을 뜻한다.

쿠키는 최소 한 칸을 차지한다. 모양은 떨어져 있는 여러 조각으로 이루어질 수 있다.

출력

쿠키를 만드는 데 필요한 초콜릿 칩 용액 노출의 최소 횟수를 출력한다.

예제3

예제 1
입력
```
5 5
-X-X-
XXXXX
XXXXX
-XXX-
--X--
```
예상 출력
```
2
```
예제 2
입력
```
4 5
--XXX
--X-X
X-XXX
XX---
```
예상 출력
```
1
```
예제 3
입력
```
5 5
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX
```
예상 출력
```
3
```