Informatica Online Judge

  전구 조작 [1060 / 0424]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 110   Total Tried : 127


The Champion of this Problem (C++) : gs19022 - 0ms / 735byte
My Best Submission (C++) : N/A

[]

Background

경곽이는 다음 그림과 같이 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열의 전구를 켜면 모든 전구를 켤 수 있게 된다.

처음 전구판의 상태가 주어질 때, 모든 전구를 끄는데 필요한 최소 조작횟수와 모든 전구를 켜는데 필요한 최소 조작횟수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 N, M이 공백으로 구분되어 입력된다.
두 번째 줄부터 N줄에 걸쳐서 M개의 0과 1이 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= N, M <= 100

[Sub-Task Info]

각 테이스 별 점수 10점씩 채점 * 10개 = 100점

Output

첫 번재 줄에 모든 전구를 끄는데 필요한 최소조작 횟수를 출력한다.
두 번째 줄에 모든 전구를 켜는데 필요한 최소조작 횟수를 출력한다.

IO Example

입력1
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

출력1
4
2

입력2
2 3
0 0 0
0 0 0

출력2
1
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]