Informatica Online Judge

  마법의 성 [0985 / 03D9]

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


The Champion of this Problem (C++) : gs16066 - ms / 1278byte
My Best Submission (C++) : N/A

[koistudy.net (unknown)]

Background

마법의 성 지하에는 마법에 걸린 공주가 갇혀 있다. 이 공주를 구하기 위해 먼 이웃나라에서 백마를 타고 왕자가 왔다. 사악한 마녀는 공주를 구하지 못하게 하기 위해 지하에 미로를 설치해 놓았는데 이 미로는 공기가 매우 희박하여 그 어떤 사람도 죽지 않고 이 미로를 통과할 수 없다. 이에 지혜로운 왕자는 다이너마이트를 준비하여 미로에서 한 군데 벽을 허물 수 있게 하였다. 하지만 이 일도 쉽지만은 않다. 과연 어떤 벽을 허물어야 가장 빠른 시간 안에 공주에게 갈 수 있을까?

Input

첫째 줄에 지하 미로의 세로의 크기와 가로의 크기를 나타내는 자연수 N과 M이 주어지고 다음 N줄에는 M개의 정수로 지하미로에 상태가 주어진다. 지나갈 수 있는 위치는 0으로, 장애물이 있는 위치는 1로 표현된다. 입구는 항상 왼쪽 제일 아래이고, 출구는 항상 오른쪽 제일 위이며 길이 없는 경우는 없다.

[입력값의 정의역]

3 <= N, M <= 100

Output

첫줄에 허물어야 하는 벽이 위에서 몇 번째 행인지, 왼쪽에서 몇 번째 열인지 그 행과 열을 출력하고, 두 번째 줄에는 그 때 지나는 블록의 수를 출력한다. 만약 벽을 허물 필요가 없다면 벽의 위치 대신 0 0을 출력한다. 단 해는 유일하다.

IO Example

입력
7 6
0 0 0 0 0 0
0 1 1 1 1 0
0 0 0 1 0 0
1 1 0 1 1 1
0 0 0 0 1 0
1 1 1 0 1 0
0 0 0 0 0 0

출력
4 6
12

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