1886번 - 프리즌 브레이크 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 711 | 155 | 91 | 17.433% |
문제
N×M 크기의 감옥이 있다. 감옥은 스코필드가 미리 뚫어 놓은 탈출구, 벽, 그리고 빈 칸으로 이루어져 있는데 각각의 모든 빈 칸에는 사람이 한 명씩 있다. 감옥 안에 있는 모든 사람들은 탈출구를 통해 탈옥을 해 내야 한다. 물론, 최대한 빨리 모든 사람이 탈출하도록 하고 싶다.
각 사람이 한 칸을 이동하는 데에는 1초가 걸리며, 하나의 탈출구를 통해서는 1초에 한 사람만 탈출을 할 수 있다. 그리고 사람들이 탈출하는 동안에는 하나의 빈 칸에 여러 명의 사람들이 있어도 된다. 감옥의 정보가 주어져 있을 때, 사람들이 모두 탈출하려면 모두 몇 초의 시간이 걸리는지 구하는 프로그램을 작성하시오.
감옥의 가장자리는 반드시 벽 또는 탈출구이며, 안쪽에는 탈출구가 없다. 탈출구가 없을 수도 있고, 감옥에는 빈 칸이 하나 이상 있다.
입력
첫째 줄에 감옥의 행의 수와 열의 수, N, M이 공백을 사이에 두고 주어진다. 그리고 N개의 줄에 걸쳐서 감옥의 정보가 주어진다. ‘X'는 벽을 의미하고 '.'은 빈 칸, 'D'는 스코필드가 미리 뚫어 놓은 탈출구 위치를 의미한다.
출력
첫째 줄에 모든 사람이 탈출을 하는 최소시간을 출력한다. 만약에 모두 탈출하는 것이 불가능하다면 “impossible"을 출력한다.
제한
- 3 ≤ N, M ≤ 12
예제 입력 1
5 5 XXDXX X...X D...X X...D XXXXX
예제 출력 1
3
예제 입력 2
5 5 XDXXX X.X.D XX.XX D.X.X XXXDX
예제 출력 2
impossible
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2006 F번
- 빠진 조건을 찾은 사람: kks227
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호