루미 알고리즘

#1473플래티넘Eldberget

PO 2019 온라인 예선코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Under en utflykt till eldbergen Yanar Dag i Azerbajdzjan (värdland för årets internationella programmeringsolympiad) har du gått vilse! Bergen har formen av ett rutnät med R rader och C kolumner. Du står längst upp till vänster i rutnätet och vill förflytta dig till utflyktsbussen som är längst ner till höger. Eftersom bussen går snart vill du gå dit så snart som möjligt. För att ta dig till bussen kan du flytta dig till en ruta direkt ovan, till höger, under eller till vänster om den du står.

På eldbergen finns det dock ett antal eldflammor, orsakade av naturgas som sipprar ut från bergen. Eftersom du har väldigt fina kläder på dig vill du inte behöva springa igenom fler eldflammor än nödvändigt. Mer specifikt är du beredd att gå genom högst K eldflammor på din väg till bussen.

Din uppgift är att beräkna hur snabbt du kan förflytta dig till bussen om du får gå genom högst K eldflammor.

Indata

Den första raden innehåller tre heltal R, C, K (2 ≤ R, C ≤ 100, 0 ≤ K ≤ 200), antalet rader och kolumner i rutnätet som eldbergen består av, samt antalet flammor du kan springa igenom.

De följande R raderna utgör en beskrivning av hur eldbergen ser ut. Den i:te av dessa rader innehåller C tecken som beskriver hur den i:te raden ser ut. Varje tecken är antingen en punkt (.) om en ruta är tom eller en fyrkant (#) om rutan innehåller en flamma. Rutan längst upp till vänster och rutan längst ned till höger är alltid punkter.

Utdata

Skriv ut ett heltal N – det minsta antalet steg du behöver för att ta dig till bussen. Om du inte kan ta dig till målet utan att gå genom fler än K flammor ska du skriva ut “nej”.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränser
120Gruppen består av ett enda testfall med K = 0; det som finns på vår affisch (https://www.progolymp.se/2019/affish2018.pdf).
27Det är alltid möjligt att ta dig till bussen, och du behöver bara gå nedåt eller höger i rutnätet.
315K = 0 och varje kolumn består av en eldpelare som börjar från toppen av kolumnen och en eldpelare som börjar från botten av kolumnen. Pelarna kan ha längd 0, och det finns alltid minst en ruta utan eld i varje kolumn.
410K = 0
519K = 1
629Inga ytterligare begränsningar.

Sample

Notera att endast Sample 1 kan förekomma i testfallsgrupp 2, och endast Sample 4 kan förekomma i testfallsgrupp 3.

예제

예제 1

입력
5 5 0
.....
#.#.#
..#.#
.#...
...#.
출력
8

예제 2

입력
6 6 1
.##...
.##.#.
.##.#.
.#..#.
.#.##.
...##.
출력
14

예제 3

입력
6 6 1
.##...
.##.#.
.##.#.
##..##
.#.##.
...##.
출력
nej

예제 4

입력
6 6 0
.###.#
.#.#.#
.#....
...##.
#.###.
#####.
출력
12

출처 표기

출처: Programmeringsolympiaden 2019년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.