경곽이는 다음 그림과 같이 N행 M열의 전구판을 가지고 있다. 전구판에 놓여있는 전구들 중 0은 불이 켜진 것이고, 1은 불이꺼진 것이다.


 0 0 1 0 1 1 
0 1 1 0 0 0
0 0 1 0 0 0
1 1 1 1 1 1
0 0 0 1 0 0

임의의 전구의 상태를 바꾸면, 이 전구와 인접한 같은 상태의 전구들은 모두 상태가 바뀐다. 이 과정은 처음 전구에 의해 상태가 바뀌는 전구에도 적용되어 더 이상 상태가 바뀌지 않을 때까지 모두 바뀐다. 예를 들어 위의 그림에서 1,1의 전구를 끄면 0이 1로 바뀌면서 상, 하, 좌, 우로 인접한 모든 전구들이 1로 바뀐다.


 1 1 1 0 1 1 
1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 1 1 1
0 0 0 1 0 0

다음으로 1행 4열의 전구를 0에서 1로 바꾸면


 1 1 1 1 1 1 
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 0 1 0 0

다음으로 5행 1열의 전구를 1로 바꾸면


 1 1 1 1 1 1 
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 0 0

마지막으로 5행 5열의 전구를 1로 바꾸면


 1 1 1 1 1 1 
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

이로써 모든 전구들이 꺼지게 된다. 즉, 총 4번의 조작으로 모든 전구를 끌 수 있다. 반대로 맨 처음 상태에서 1행 3열, 1행 5열의 전구를 켜면 모든 전구를 켤 수 있게 된다. 처음 전구판의 상태가 주어질 때, 모든 전구를 끄는데 필요한 최소 조작횟수와 모든 전구를 켜는데 필요한 최소 조작횟수를 구하는 프로그램을 작성하시오.

전구 조작

문제 설명

입력

출력

예제

코드 제출

로그인

LOGIN