시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1864 | 763 | 545 | 41.039% |
세준이는 위험한 지역에서 탈출하는 게임을 하고 있다. 이 게임에는 세준이가 들어갈 수 없는 죽음의 구역이 있고, 들어가서 한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역이 있다. 그리고, 자유롭게 생명의 위협없이 움직일 수 있는 안전한 구역이 있다. (안전한 구역은 죽음의 구역과 위험한 구역을 제외한 나머지 이다.)
세준이는 (0, 0)에서 출발해서 (500, 500)으로 가야 한다. 세준이는 위, 아래, 오른쪽, 왼쪽으로만 이동할 수 있다. 현재 세준이는 (0, 0)에 있다. 그리고, 게임 판을 벗어날 수는 없다.
세준이가 (0, 0)에서 (500, 500)으로 갈 때 잃는 생명의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 반대 모서리이다. 그 다음 줄에는 죽음의 구역의 수 M이 주어진다. 다음 줄부터 M개의 줄에는 죽음의 구역의 정보가 위험한 구역의 정보와 같이 주어진다. 주어지는 구역은 모두 겹칠 수 있으며, 서로 다른 구역이 겹칠 때는, 더 심한 구역이 해당된다. 예를 들어, 죽음+위험 = 죽음, 위험+안전 = 위험, 위험+위험 = 위험, 죽음+안전 = 죽음이다. 위험한 구역이 아무리 겹쳐도 생명은 1씩 감소된다. 생명의 감소는 구역에 들어갈 때만, 영향을 미친다. 예를 들어, (500, 500)이 위험한 구역일 때는, (500, 500)에 들어갈 때, 생명이 1 감소되지만, (0, 0)이 위험한 구역이더라도 생명은 감소되지 않는다. 마찬가지로, (0, 0)이 죽음의 구역이더라도 세준이는 이미 그 곳에 있으므로 세준이에게 영향을 미치지 않는다. N과 M은 50보다 작거나 같은 자연수이다.
첫째 줄에 정답을 출력한다. 만약 (500, 500)으로 갈 수 없을 때는 -1을 출력한다.
1 500 0 0 500 1 0 0 0 0
1000
0 0
0
2 0 0 250 250 250 250 500 500 2 0 251 249 500 251 0 500 249
1000
2 0 0 250 250 250 250 500 500 2 0 250 250 500 250 0 500 250
-1