3656번 - 수영장 만들기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 128 MB | 131 | 64 | 39 | 41.489% |
문제
상근이는 사람들에게 수영장을 만들어주고 있다. 이번에는 정인이의 앞 마당에 수영장을 만들어 주려고 한다.
수영장 부지는 w×h크기이고, 1×1 크기의 정사각형 구역으로 나누어져 있다.수영장은 0개 또는 그 이상의 구멍 구역으로 이루어져 있다. 구멍을 뚫은 곳에는 나중에 물이 채워질 예정이다.
수영장을 만들기 전에 각 구역은 구멍('.')이거나 잔디('#')이다. 이 땅을 수영장으로 만들려면 아래와 같은 규칙을 지켜야 한다.
- 구역을 그 자체로 놔둘 수 있다. 이때 드는 비용은 없다.
- 잔디였던 구역에 구멍을 파는데 드는 비용은 d원이다.
- 구멍이였던 구역에 구멍을 막고 잔디를 심는데 드는 비용은 f원이다.
- 수영장의 경계가 되는 각 변(잔디와 구멍 사이)에는 물이 세지 않기 위한 경계 처리를 해야 한다. 이 작업은 한 변당 b원이 든다.
- 수영장 부지의 가장 바깥 행과 열은 잔디이어야 한다.
현재 수영장 부지의 땅 정보가 주어졌을 때, 수영장을 만드는데 가장 싼 비용을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.
각 테스트 케이스의 첫째 줄에는 수영장 부지의 크기 w와 h가 주어진다. (2 ≤ w, h ≤ 50) 다음 줄에는 d, f, b가 주어진다. (1 ≤ d, f, b ≤ 10,000) 다음 h개 줄에는 수영장을 만들 부지의 정보가 주어진다.
출력
각 테스트 케이스에 대해서, 수영장을 만드는데 드는 비용의 최솟값을 출력한다.
예제 입력 1
3 3 3 5 5 1 #.# #.# ### 5 4 1 8 1 #..## ##.## #.#.# ##### 2 2 27 11 11 #. .#
예제 출력 1
9 27 22
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 F번
- 문제를 번역한 사람: baekjoon
- 문제의 오타를 찾은 사람: choiking10
- 시간 제한을 수정한 사람: kks227
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호