20046번 - Road Reconstruction 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 1239 | 590 | 490 | 48.371% |
문제
홍수의 발생으로 인해 도시의 도로들이 유실되어 많은 ICP(International Computational Plan) 시민들이 불편을 겪고 있다. 도시는 아래와 같은 격자 형태로 표현이 된다고 가정하자. 검정색 단위 격자가 ‘단위도로’를 의미하며 흰색 단위 격자는 도로가 없었거나 유실된 상태를 의미한다. X로 표시된 단위 격자는 도로를 건설할 수 없는 곳을 의미한다.
도시의 차들은 단위 도로 상에서 가로나 세로 방향으로만 움직인다고 가정했을 때 도시의 기능을 회복시키기 위해 맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 도시의 차들이 가는 경로를 만들기 위해 필요한 최소한의 도로 건설 비용을 계산하고자 한다. 단위 도로 하나를 건설하기 위해 1 또는 2 의 비용이 소요된다고 가정하자. 위 그림에서는 흰색 단위 격자에 단위 도로 하나를 건설하기 위해서는 1 의 비용이 든다고 가정한다.
위와 같이 회색으로 표시된 단위 도로들을 4 의 비용으로 건설하면 목적을 달성할 수 있다.
도시가 위와 같이 격자 형태로 주어졌을 때 맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 가는 경로를 만들기 위해 필요한 최소 도로 건설 비용을 구하는 프로그램을 작성하시오.
입력
입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 열의 정보를 나타내는 n개의 숫자가 주어진다. 각 열의 정보는 정수 0, 1, 2, -1 로 나타내며 0 은 단위도로가 이미 존재하는 것을, 즉, 도로에 유실이 없는 상태, 1 은 단위 도로가 없고 1 의 비용으로 도로를 건설할 수 있는 단위 격자, 2 는 단위 도로가 없고 2 의 비용으로 도로를 건설할 수 있는 단위 격자를 의미한다. -1 은 X로 표시된 단위 격자로 그 위치에 단위 도로를 건설할 수 없는 상태를 의미한다.
출력
출력은 표준출력을 사용한다. 도시의 맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 가는 경로를 만들기 위해 필요한 최소한의 도로 건설 비용을 한 줄에 출력한다. 해당 경로를 건설할 수 없을 때는 -1 을 출력한다.
예제 입력 1
2 3 1 -1 -1 1 -1 2
예제 출력 1
-1
예제 입력 2
2 3 -1 1 -1 1 1 -1
예제 출력 2
-1
예제 입력 3
6 8 0 0 1 1 -1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 -1 1 0 1 1 1 -1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 1 1 0
예제 출력 3
4
예제 입력 4
6 8 2 0 1 1 -1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 -1 1 0 1 1 1 -1 2 1 1 0 1 1 1 0 2 0 0 0 -1 1 1 0 0 0 1 2 2 0
예제 출력 4
8
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호