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

문제

세준이는 N*M크기의 전구를 가지고 있다. 이 전구는 한번 만지면 자신을 포함해서 인접한 8개 (위, 아래, 왼쪽, 오른쪽, 대각선)의 상태가 바뀐다. (켜져 있는 거 -> 꺼짐, 꺼진거 -> 켜짐)

현재 전구의 상태가 주어질 때, 세준이는 불을 전부 키려고 한다. 세준이가 전구를 만져야하는 회수의 최소값을 출력한다.

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 상태가 주어진다. * : 켜짐, . : 꺼짐 N,M <=8

출력

첫째 줄에 최소값을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력

3 3
**.
**.
..*

예제 출력

2

힌트

출처