Informatica Online Judge

  다이너마이트 [0456 / 01C8]

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


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

[]

Background

입구가 (n,1)이고 출구가 (1,m)인 미로가 있다. 창은이는 이 미로를 가장 빠른 시간에 빠져나가고자 한다.

...라는 문제는 많이 풀어봤다. 식상한 미로찾기 문제가 싫은 창은이는 다이너마이트 하나를 갖고 미로에 들어갔다. 다이너마이트 하나는 벽 하나를 부술 수 있다고 하자. 이 때, 미로를 빠져나가는데 드는 최소의 시간을 구하여라.

Input

첫째 줄에 미로의 세로의 크기와 가로의 크기를 나타내는 자연수 n과 m이 주어진다.
(1<=n,m<=100)
그 다음 n개의 줄에 걸쳐 m개의 격자 정보가 주어진다. 지나갈 수 있는 위치는 0으로, 장애물이 있는 위치는 1로 표현된다. 입구는 항상 왼쪽 제일 아래이고, 출구는 항상 오른쪽 제일 위이다. 한 군데 벽을 허물고도 길이 없는 경우는 없다.

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


출처 : 윤형석(서울대 컴퓨터공학과, 2009 IOI 금메달)

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