불 켜기
시간 제한2초메모리 제한128 MB
N×M(N,M≤8) 보드에서 누르면 자신과 8방향 이웃의 불을 모두 뒤집는 스위치를 이용해 모든 불을 켜는 데 필요한 최소 누름 횟수를 구하는 문제입니다.
문제
세준이는 N×M 크기의 보드를 가지고 있습니다. 보드는 1×1 크기의 칸으로 나뉘어 있고, 각 칸에는 전구가 하나씩 있습니다.
전구 하나를 누르면 그 전구의 상태가 반전됩니다. 켜져 있던 전구는 꺼지고, 꺼져 있던 전구는 켜집니다. 전구는 매우 민감해서, 어떤 전구를 누르면 상하좌우와 대각선을 포함한 주변 8칸의 전구도 함께 반전됩니다.
현재 전구의 상태가 주어질 때, 모든 전구를 켜기 위해 눌러야 하는 전구 수의 최솟값을 구하세요.
입력
첫째 줄에 N과 M이 주어집니다.
둘째 줄부터 N개의 줄에 보드의 상태가 주어집니다. N과 M은 8 이하입니다. *는 켜진 전구, .는 꺼진 전구를 의미합니다.
출력
첫째 줄에 모든 전구를 켜기 위해 눌러야 하는 전구 수의 최솟값을 출력합니다. 불가능하면 -1을 출력합니다.