| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 64 MB | 302 | 70 | 59 | 24.790% |
MRT Corp has recently hired you, one of the most talented programmers in the country, to assist in building MRT tracks in the country.
To begin with, you are given a square grid map of size N x N, detailing the number of people, C residing in each grid segment. Since constructing your tracks would require all inhabitants of the utilised land to relocate, you are to decide on a potential railway connecting train stations A and B, with the coordinates (Ax, Ay) and (Bx, By) respectively, such that the number of people forced to relocate are kept to a minimum and output that number. Do note that there may be certain areas in which you cannot build your train tracks (e.g. unstable land, hills etc.).
You are also reminded that you cannot build diagonal train tracks and only build in the 4 main directions (e.g. left, right, up, down).
Line 1: An integer N, the length of the square grid of the map. (2 ≤ N≤ 400)
Line 2: Four integers Ax, Ay, Bx and By which signifies the x and y-coordinates (from top-left to bottom-right) of the two stations A and B. You will be guaranteed that the two train stations will be situated at distinct locations. (1 ≤ Ax, Ay, Bx, By ≤ N)
Line 3 to (N+2): Nintegers with a value, C each detailing the number of inhabitants of a particular area and separated by spaces. Areas in which you are not allowed to build train tracks on will be given a value of -1. (-1 ≤ C≤ 1,000,000)
A single line stating the minimum number of inhabitants that will have to be relocated. Output -1 if it is impossible to construct the tracks without building on the areas in which you are not allowed to build tracks.
5 3 1 5 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
6
5 3 1 5 4 1 1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1 -1 1 1 1
-1
5 1 3 4 5 10 30 20 50 10 10 20 -1 25 10 99 10 -1 10 10 10 10 -1 10 10 10 10 -1 99 12
363