Informatica Online Judge

  Reverse Game [2127 / 084F]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[24th 안유진]
Writer ID : [gs16055]

Background

리버스 보드게임은 검은 색, 또는 하얀 색 작은 원판을 8x8의 판 위에 늘어놓는 보드 게임이다. 경기규칙은 다음과 같다.

1. 처음에는 정 중앙에 흑백 2개의 돌을 교차로 놓고 게임을 시작한다.

2. 돌을 놓을 때, 자신이 놓을 돌과 자신의 돌 사이에 상,하,좌,우,대각선으로 상대편의 돌이 있어야 돌을 놓을 수 있으며, 돌을 놓게 되면, 상대편의 돌을 뒤집어 자기편의 돌로 만들 수 있다.

3. 한 쪽이 돌을 놓을 수 없는 상황이 발생한다면 패스(Pass)라고 하여 상대편 차례가 된다.

4. 흑과 백 모두 돌을 놓을 곳이 없으면 게임이 끝나고, 돌이 더 많은 쪽이 승리하게 된다. 흑백돌이 놓여지지 않는 칸이 있더라도 마찬가지. 양측 돌의 수가 똑같으면 무승부가 된다.

여러분은 두 고수 롬멜과 몽고메리의 리버스 대결을 구경 중이다. 여러분은 롬멜을 도와 진행 중인 판에서 롬멜이 가장 많은 돌을 뒤집을 수 있는 위치와 개수를 슬쩍 알려주도록 하자.

롬멜은 백돌을 잡고 있고, 게임 판의 크기는 1000x1000보다 작다.

Input

첫째 줄에는 N*M 판의 크기 N(가로), M(세로)이 입력된다.

그 다음에는 m줄에 걸쳐 n칸의 현재 게임 판의 상황이 주어진다.

흰 돌은 0, 검은 돌은 1, 빈칸은 –1로 표현된다.

Output

롬멜이 가장 많은 돌을 뒤집을 수 있는 개수와 다음 줄에 좌표(n,m)를 출력한다.

최대로 돌을 뒤집을 수 있는 곳이 두 곳 이상이라면 아무거나 하나만 출력한다. 만약 롬멜이 둘 수 있는 곳이 없다면 pass를 출력한다.

IO Example

입력1
8 8
-1 1 1 1 1 1 1 -1
-1 -1 0 0 0 0 -1 -1
-1 1 1 0 0 0 1 1
1 1 0 0 0 0 1 1
-1 1 1 1 1 1 1 1
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
6
7 6

입력2
8 8
-1 -1 0 -1 1 1 1 1
-1 -1 -1 0 0 1 1 1
0 0 0 0 0 0 1 1
0 -1 0 1 0 0 -1 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 -1 1
0 -1 0 0 -1 -1 -1 -1
-1 -1 -1 1 1 1 –1 -1

출력2
pass

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