시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 256 MB | 792 | 220 | 166 | 29.964% |
엔터프라이즈호가 클링온에게 포위되었다! 가장 빠른 시간 내에 나갈 수 있는 탈출 루트를 찾고 그 시간을 출력하라.
직사각형의 평면이 입력으로 주어지며, 이는 엔터프라이즈호와 클링온 전투선들의 위치들을 의미한다. 클링온 전투선은 몇 가지의 클래스로 나누어지며, 각 클래스의 클링온 전투선을 엔터프라이즈호가 무력화 시키는 데에 걸리는 시간도 입력으로 주어진다. 엔터프라이즈호는 탈출하는 경로에 있는 모든 클링온 전투선을 무력화 시키며 입력된 평면의 가장자리로 탈출한다. 입력된 평면의 단위 사각형은 꼭짓점이 아닌 가장자리로만 연결된다. (즉, 각 단위 사각형은 4개의 이웃 단위 사각형을 갖는다.)
첫째 줄에 테스트 케이스의 개수 T (2 ≤ T ≤ 100)가 주어진다.
각 케이스는 첫 줄에 세개의 숫자 K, W, H가 주어진다.
K (1 ≤ K ≤ 25)는 클링온 전투선의 클래스 개수를 의미한다.
W (1 ≤ W ≤ 1000)는 평면의 폭을 의미한다.
H (1 ≤ H ≤ 1000)는 평면의 높이를 의미한다.
다음 K 줄에는 클링온 전투선의 클래스 이름과 무력화시키는 데에 걸리는 시간이 주어진다.
클링온 전투선의 클래스 이름은 알파벳 대문자로 주어지며, "E" 가될 수 없다. 클래스의 이름은 겹칠 수 없다.
무력화시키는 데에 걸리는 시간은 '분'을 나타내며 0 이상, 100,000 이하이다.
다음 H 줄에는 W 개의 알파벳 대문자가 주어진다. (각 문자 사이에는 공백이 없다.)
H 줄의 W 개 문자 중,
"E"는 엔터프라이즈호의 위치를 의미하며, 반드시 하나만 주어진다.
"E"가 아닌 다른 모든 문자는 해당 단위 평면에 위치한 클링온 전투선의 클래스이고, 반드시 위 K 줄에서 무력화시키는 데에 걸리는 시간과 함께 주어진다.
엔터프라이즈호가 탈출하는 데에 걸리는 최소 시간을 정수로 출력하라.
2 6 3 3 A 1 B 2 C 3 D 4 F 5 G 6 ABC FEC DBG 2 6 3 A 100 B 1000 BBBBBB AAAAEB BBBBBB
2 400
ICPC > Regionals > North America > Pacific Northwest Regional > 2013 Pacific Northwest Region Programming Contest E번