문제 번호 3544 --전광판 전구 조작

3544: 전광판 전구 조작

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 7  해결 문제 수: 5
[제출][채점상황][게시판][:]

문제 설명

길동이는 아래 그림과 같이 M*N 개인 전광판 위에 놓여있는 켜져있는 전구(흰색)와 꺼져 있는 전구(검은색)들을 가지고 실험을 한다.

임의의 전구 x에 대해서 상, 하, 좌, 우로 인접한 4개의 전구들을 X의 이웃이라고 한다.

길동이는 위의 전구들 중에서 하나를 선택해서 전구를 켜거나 끌 수 있다.

그러면 이 전구의 이웃이고 같은 상태로 있는 전구들도 상태가 바뀐다. 

계속해서 반복적으로 상태가 바뀐 전구의 이웃들 또한 같은 상태로 바뀐다.

 예를 들어, 위의 그림에서 1번을 켜면 'ㄷ'자 모양의 꺼진 전구들은 모두 켜지므로 아래의 그림과 같이 된다.

그런 다음 전구 3을 켜면 아래와 같이 된다.

그리고 전구 6을 켜고, 마지막으로 5를 켜면 모든 전구는 켜진 상태가 된다.

따라서 4번의 조작으로 모든 전구가 켜진다.

같은 방법으로 처음 상태에서 전구 2와 전구 4를 끄는 두 번의 조작으로 모든 전구가 꺼진 상태로 바꿀 수 있다.

켜져 있거나 꺼져 있는 전구들을 조작하여 모두 켜진 상태가 되도록 하는 최소 조작횟수와 모든 꺼진 상태로 되도록 하는 최소조작횟수를

찾는 프로그램을 작성하라

입력

첫 줄에 전광판의 크기를 나타내는 세로 길이 M과 가로 길이 N이 입력된다. (2<=M,N<=100인 자연수)

둘째줄 부터  M줄에 걸쳐 N열 만큼의 전구들의 상태가 주어진다. 이때 켜진 상태는 1, 꺼진 상태는 0으로 입력된다.

출력

모든 전구를 켜기 위한 최소 조작횟수와 모두 끄기 위한 최소조작횟수를 각각 공백으로 구분하여 출력하라.

입력예시

5 6
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

출력예시

4 2

도움말

출처

[제출][채점상황]