dlaud5379   1년 전

(Kagi Translate로 영어로 번역한 텍스트를 중역했습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

잇창명은 양고기를 재울 마리네이드를 만들기 위해 마법의 미로를 통과해야 한다. 미로는 벽, 빈 공간, 마리네이드 재료로 이루어져 있다.

미로는 가로 M, 세로 N의 격자로 표현할 수 있다. 미로의 각 칸은 벽('#'), 빈 공간('.'), 마리네이드 재료('N'), 입구('U'), 출구('I') 중 하나이다. 재료가 있는 칸은 정확히 K개이고, 입구와 출구는 정확히 하나씩 존재한다. 잇창명은 입구를 통해 미로에 들어와서 출구로 나가야 하며, 벽을 제외한 모든 칸을 횟수 제한 없이 자유롭게 오갈 수 있다. [역자 주: '미로 밖의 칸으로 나갈 수는 없다.'가 빠져 있습니다.] 잇창명은 매 초마다 상하좌우로 한 칸씩 이동할 수 있다.

미로의 정보가 주어졌을 때, 잇창명이 마리네이드 재료를 모두 모으고 출구로 나가는 데 드는 최소 시간을 구하는 프로그램을 작성하여라.

저희 양고기 먹고 싶어요 ㅠㅠ -운영진

입력

첫째 줄에 N, M, K가 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ 16)

둘째 줄부터 N줄에 걸쳐 미로의 정보가 주어진다. 각 줄에는 M개의 문자로 이루어진 문자열이 주어지며, 문자열은 '#', '.', 'N', 'U', 'I'로만 이루어져 있다. 'N'은 미로 전체에 걸쳐 정확히 K개 주어진다. [역자 주: '마리네이드 재료를 모두 모으고 출구로 나갈 수 있는 입력만 주어진다.'가 빠져 있습니다.]

출력

문제의 정답을 한 줄로 출력한다.

서브태스크

번호배점제한
130N, M ≤ 50, K ≤ 6
230K ≤ 8
340추가 제한 조건이 없다.

댓글을 작성하려면 로그인해야 합니다.