래환이의 아이브 콘서트 이야기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N×M 격자에서 행 번호와 가운데 열까지의 거리의 합이 최소인 빈 좌석을 찾고, 빈 좌석이 없으면 -1을 출력한다.

난이도: 쉬움10점 중 2점
유형: 구현, 완전 탐색, 배열
정답자: 아직 제출이 없습니다

문제

래환이는 오랜만에 열리는 아이브 콘서트에 가기 위해 좌석을 예매하려고 한다. 공연장은 무대가 앞에 있고, 좌석은 무대 뒤로 $N \times M$ 형태로 배치되어 있다. 단, $M$ 은 홀수이다.

아래 그림과 같이 예매 페이지에서는 현재 좌석의 예매 상태를 보여주며, 각 좌석은 비어 있거나 이미 예매된 상태이다. 이 중에서 비어 있는 좌석만 예매할 수 있다.

래환이는 아이브가 가장 잘 보이는 위치를 원하기 때문에, 다음 값을 최소화하는 좌석 $R$ 행 $C$ 열을 예매하고자 한다: $\mathrm{Distance} = R + \left| \frac{M+1}{2} - C \right|$ 즉, 무대에 가까운 앞줄이면서도 가운데에 가까운 좌석을 가장 선호한다. 단, 행 번호는 위쪽부터 $1$ 번, 열 번호는 가장 왼쪽부터 $1$ 번이다.

래환이를 위해 예매가 가능한 좌석 중에서 $\mathrm{Distance}$ 가 가장 작은 좌석을 찾아주자.

입력

첫 번째 줄에 두 개의 정수 $N$ , $M$ 이 공백으로 구분되어 주어진다. $(1 \le N,M \le 100)$

다음 $N$ 개의 줄에는 좌석 예매 상태를 나타내는 $M$ 개의 정수가 공백으로 구분되어 주어진다. $0$ 은 빈 좌석, $1$ 은 이미 예매된 좌석을 의미한다.

출력

예매할 수 있는 좌석이 없는 경우 -1을 출력한다.

예매할 수 있는 좌석이 있는 경우 $\mathrm{Distance}$ 가 가장 작은 좌석의 행 번호와 열 번호를 공백으로 구분하여 출력한다.

정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.

예제3

예제 1

입력

예상 출력

1 3

예제 2
입력
```
3 3
1 1 1
1 1 1
1 1 1
```
예상 출력
```
-1
```
예제 3
입력
```
3 5
1 1 1 1 1
1 1 1 1 1
0 0 1 0 0
```
예상 출력
```
3 2
```