Informatica Online Judge

  그랩을 피해라 [2243 / 08C3]

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


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

[34th 안민형]

Background

승한이는 오늘도 실버에 가기 위해 열심히 리그오브레전드에서 랭크 게임을 하고 있다.
마스터 이를 하던 승한이는 바텀에서 cs를 먹던 중 한타를 이긴 팀원들에게서 바론을 먹자는 말을 듣는다.
정글러인 승한이는 반드시 가야 하는 상황. 승한이는 바로 바텀에서 탑으로 출발한다.
하지만 문제가 있다. 상대팀에 블리츠크랭크가 아직 살아 있었다. 탑으로 가다가 블리츠크랭크의 그랩을 맞는다면
함께 남아있는 상대 미드에게 꼼짝없이 죽을 것이다. 승한이가 무사히 바론을 먹으러 가도록 도와주자.

승한이의 현재 위치는 (1, 1)이고, 바론은 (n, n)에 있다. 승한이는 1초마다 1칸씩 이동한다.
블리츠크랭크는 총 k대 있다.
특별 모드라서 상대 블리츠크랭크는 그랩 쿨타임 t초마다 상, 하, 좌, 우 네 방향으로 동시에 그랩을 날린다.
각각의 블리츠크랭크의 쿨타임 t와 사거리 r은 모두 같다.
블리츠크랭크가 그랩을 날릴 때 승한이가 그랩 사거리 안에 있거나 도중에 블리츠크랭크를 만나면
꼼짝없이 죽고 만다. 또한 최대한 빨리 바론을 먹으러 가야 하기 때문에 가능한 한 최단 거리를 구하고자 한다.

Input

첫 줄에 n(1<=n<=1000),k ,t ,r이 순서대로 주어진다.
두번째 줄부터 k+1번째 줄까지 각 블리츠크랭크의 위치 a,b가 입력된다.
k+2번째 줄부터 n+k+1번째 줄까지 승한이가 지나다닐 지도가 주어진다.
승한이가 다닐 수 있는 곳은 1, 그렇지 않은 곳은 0으로 입력된다. 시작 위치와 바론 위치는 항상 1이다.

Output

승한이가 그랩에 끌리지 않고 바론까지 갈 수 있는 최단 거리를 출력한다.
만약 그랩에 끌릴 수밖에 없거나 벽으로 막혀있어 바론까지 갈 수 없으면, "Bronze"를 출력한다.

IO Example

입력1
10 1 2 5
0 4
1 1 1 1 1 1 0 1 1 1
0 1 1 0 1 1 0 0 1 0
0 1 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 0 1
0 0 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 0 0 1 1 1
1 0 1 0 1 1 1 0 1 1
0 1 1 1 1 1 1 1 0 1
0 0 0 1 0 0 1 0 1 1

출력1
18

입력2
10 1 1 5
7 0
1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 0 1 0 1 1
1 1 1 0 0 1 0 0 0 0
1 1 0 1 0 1 0 1 1 1
1 1 1 0 1 0 0 1 0 1
0 1 1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 0
1 1 0 0 0 1 1 1 1 0
1 1 1 1 1 1 0 1 1 1

출력2
Bronze

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