시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB193554030.075%

문제

세준이는 N×M 크기의 보드를 가지고 있고, 보드는 1×1 크기의 칸으로 나누어져 있다. 각 칸에는 전구가 하나씩 있다. 전구를 한번 만지면 전구의 상태가 반전된다. 즉, 켜있는 전구를 만지면 불이 꺼지고, 불이 꺼진 전구를 만지면 켜진다. 전구는 매우 민감하기 때문에, 전구를 만질 때, 인접한 8개 (위, 아래, 왼쪽, 오른쪽, 대각선) 전구의 상태도 반전된다.

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

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 상태가 주어진다. N과 M은 8보다 작거나 같고, '*'는 불이 켜진 전구, '.'는 불이 꺼진 전구를 의미한다.

출력

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

예제 입력 1

3 3
**.
**.
..*

예제 출력 1

2

예제 입력 2

1 2
.*

예제 출력 2

-1

예제 입력 3

5 5
*****
*...*
*...*
*...*
*****

예제 출력 3

1

예제 입력 4

4 4
*...
**..
..**
...*

예제 출력 4

10

출처