시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 211 | 70 | 61 | 52.137% |
격자로 된 지도에 n명의 어린이와 n개의 집이 있다. 각각의 단위 시간동안, 모든 어린이가 한 단위만큼 움직일 수 있다. (수평이나 수직의 인접한 점으로) 당신은 각각의 어린이가 집에 들어갈 때까지, 1번 움직일 때마다 1달러의 여행비를 지불해야한다. 각각의 집에는 오직 한 명의 어린이만 들어갈 수 있다.
당신의 목표는 n명의 어린이들을 n개의 다른 집으로 보내는데 지불해야하는 비용을 최소화 하는 것이다. 입력은 지도인데, '.' 은 빈 공간을 의미하고 'H'는 집을 의미하고 'm' 은 어린이를 의미한다.
격자로 된 지도에서 각각의 점을 격자라고 간주한다. 그리고 이 격자에 n명의 어린이를 동시에 놓을 수 있다. 또한, 한 어린이가 집으로 들어가지 않고 집의 격자로 움직이는 것은 가능하다.
입력으로 하나에서 여러 개의 테스트 케이스가 있다. 각각의 케이스의 첫 줄은 N과 M의 두개의 정수이다. N은 지도의 행(row)의 개수이고, M은 지도의 열(column)의 개수이다. 입력의 나머지는 N개의 줄 지도를 묘사한다. N와 M은 둘다 2~100 사이로 가정한다. 지도에서 'H'와 'm'의 개수는 같다. 그리고 최대 100개의 집이 있을 수 있다.
N과 M 을 0 0 으로 입력하면 입력이 종료된다.
각각의 테스트 케이스에서 출력의 첫 줄은 하나의 정수이다. 그것은 지불해야할 최소한의 달러의 양이다.
2 2 .m H. 5 5 HH..m ..... ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... 0 0
2 10 28
ICPC > Regionals > North America > Pacific Northwest Regional > 2004 Pacific Northwest Region Programming Contest E번