시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 572 | 169 | 131 | 28.112% |
일요일 밤, 내일 학교에 가는 것이 괴로워지기 시작했다.
학교에 가지 않을 핑계를 만들기 위해서, 집에서 학교로 가는 길에 벽을 잘 세워 집에서 학교로 가는 길을 모두 막기로 결정하였다.
학교와 집이 있는 동네는 N*M의 칸으로 이루어져있다. 집은 (1, 1)에 위치하고, 학교는 (N, M)에 위치한다.
각각의 칸은 3가지 종류로 나뉜다.
우리는 3번 종류의 칸에 적절히 벽을 세워서 집에서 학교로 가는 길을 막을 것이다. 단, 돈을 절약하기 위해서 비용을 최소로 하고 싶다. 다만 어떻게 벽을 지어도 막을 수 없는 경우가 있을 수 있는데, 이러한 경우도 판단해서 알려주어야 한다.
집에서 학교로 이동할 때는 상하좌우로만 이동할 수 있으며(대각선 방향으로는 이동할 수 없다), 주어진 격자판(N*M) 밖으로 이동할 수 없다. 또한, 집과 학교가 위치한 칸은 벽을 세울 수 없는 칸임이 보장된다.
첫 번째 줄에는 지도의 행의 수 N, 열의 수 M이 공백을 사이로 주어진다. (2 ≤ N, M ≤ 300) 다음 N 줄에는 각각 M 개 정수가 주어진다. -2는 벽이 있음을 의미하고, -1은 벽을 세울 수 없는 장소를 의미하며, 0 이상의 정수는 벽을 세울 수 있는 장소이며, 정수는 벽을 세우는 비용을 의미한다. 비용 값은 10억을 넘지 않는 정수이다. i 번째 줄의 j 번째 문자는 (i, j)의 정보를 나타낸다.
집과 학교가 위치한 칸((1, 1)와 (N,M))에는 -1가 들어옴이 보장된다.
첫째 줄에 학교를 갈 수 없게 만드는 최소 비용을 출력한다. 단, 학교를 갈 수 없게 길을 막을 수 없다면, -1을 출력한다
3 3 -1 1 -2 1 1 1 1 1 -1
2
5 5 -1 -1 5 -2 -2 -1 5 7 8 4 -2 5 -2 9 1 -2 8 11 2 -1 -2 9 1 -1 -1
4
5 5 -1 -1 -1 -2 -2 -1 5 -1 -1 -1 -2 -2 -2 9 -1 -2 8 11 2 -1 -2 9 1 -1 -1
-1
예제1 설명
..# .*. .*.
으로 막으면 가능하다,
University > 경인지역 6개대학 연합 > shake! 2017 B번