Problem B
Djur
I ett rutnät med $R$ rader och $C$ kolumner står en varg på rutan $(1, 1)$ och en kanin på rutan $(R, C)$. Vargen vill gå till rutan $(R, C)$ och kaninen vill gå till rutan $(1, 1)$. Det finns dock ett problem: om de två vägarna korsar varandra kommer vargen att följa kaninen och jaga den. Nu undrar vi, givet hur rutnätet ser ut, kan du hitta en vägbeskrivning för kaninen och vargen så att vägarna inte korsar varandra? Start- och slutrutorna ($(1, 1)$ och $(R, C)$) räknas inte med i vägen.
Indata
Den första raden innehåller två heltal: $R, C$. I alla testfall gäller det att $2 \leq R \cdot C \leq 2 \cdot 10^5$.
Sedan följer ett $R \times C$ rutnät. Varje ruta är antingen “.” som betyder en tom ruta, eller “#” som betyder ett hinder.
Det är garanterat att rutorna (1,1) och (R,C) är tomma.
Utdata
Skriv ut NO om det inte finns två vägar som uppfyller kraven i uppgiften.
Annars skriv ut en rad med YES. Skriv sedan ut ett rutnät där du markerar kaninens väg med “K” och vargens väg med “V”. Notera att alla hinder måste förbli hinder när du skriver ut rutnätet och att alla tomma rutor som inte är en del av vägen måste förbli tomma rutor. En väg måste vara sammanhängade.
Om du använder C++ kan det vara bra att använda ’\n’ istället för endl för att inte riskera få Time Limit Exceeded på en fungerande lösning.
Poängsättning
Din lösning kommer att testas på en antal testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$9$ |
Det finns inga hinder |
|
$2$ |
$10$ |
$R \cdot C \leq 10$ |
|
$3$ |
$20$ |
$R = 3$ |
|
$4$ |
$25$ |
$R \cdot C \leq 1000$, och det finns garanterat en lösning där vargen enbart går ned och till höger, och kaninen enbart upp och till vänster |
|
$5$ |
$36$ |
Inga ytterligare begränsningar |
Notera att vissa exempelfall inte är giltiga i alla testfallsgrupper.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 .# .. |
NO |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 ... .#. ... |
YES .VV K#V KK. |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 10 ........## ..##.##.## #....##... ###....##. ###.##.#.. #......### #.###..### #...#..... #.#.#..... ########.. |
YES .VVVV...## KK##V##.## #KKKV##... ###KVVV##. ###K##V#.. #..KKKV### #.###KV### #...#KVVVV #.#.#KKKKV ########K. |
| Sample Input 4 | Sample Output 4 |
|---|---|
4 7 .....## ..#.... ..##... ....... |
YES .VVVV## KK#.VVV .K##..V .KKKKK. |
| Sample Input 5 | Sample Output 5 |
|---|---|
16 14 .............. .............. ############.. ...........#.. ...........#.. ..#######..#.. ..#.....#..#.. ..#.....#..#.. ..#..#.....#.. ..#..#.....#.. ..#..#######.. ..#........... ..#........... ..############ .............. .............. |
YES .VVVVVVVVVVVVV KKKKKKKKKKKKKV ############KV KKKKKKKKKKK#KV KVVVVVVVVVK#KV KV#######VK#KV KV#VVVVV#VK#KV KV#VKKKV#VK#KV KV#VK#KVVVK#KV KV#VK#KKKKK#KV KV#VK#######KV KV#VKKKKKKKKKV KV#VVVVVVVVVVV KV############ KVVVVVVVVVVVVV KKKKKKKKKKKKK. |
