Informatica Online Judge

  Othello [2218 / 08AA]

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


The Champion of this Problem (C++) : gs16036 - 5ms / 1013byte
My Best Submission (C++) : N/A

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

Background

오델로 보드게임은 검은 색, 또는 하얀 색 작은 돌을 직사각형 판 위에 늘어놓는 보드 게임이다. 경기규칙은 다음과 같다.

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]