Problem H
Sjön Sjön Cleanup
The water in LTH’s own lake sjön Sjön has for millennia been a source of intense disgust. Now, in preparation for next years nollning, an attempt will be made to clean up the water in sjön Sjön by pouring a special cleaning solution into the lake.
The area around sjön Sjön can be modeled as a two dimensional grid where each cell is either water or land. Wind conditions cause the water in each water cell to flow in one of the four cardinal directions: north, south, east or west.
There may be islands in sjön Sjön, which are made up of land cells that are not connected to the edge of the grid by other land cells. All cells at the edge of the grid are land cells, and a land cell is only directly connected to its four immediate neighbors (not its four diagonal neighbors).
The cleaning solution will be poured into sjön Sjön from various points along the lake’s shoreline. This means that the solution can only be poured into water cells that have at least one non-island land cell among its four immediate neighbors.
Once poured into the lake, the cleaning solution will follow the flow of the water and clean the first $S$ water cells it enters (including the cell which the solution was initially poured into). Following the flow of the water means that solution repeatedly moves into the neighboring cell which the water in the current cell flows towards. If the solution reaches a land cell it stops moving.
Given the map of sjön Sjön, help the LTH students to minimize the number of shoreline cells that they need to pour cleaning solution into, while still making sure that every water cell in sjön Sjön becomes cleaned.
Input
The first line contains three integers $N$, $M$, and $S$ ($3 \leq N, M \leq 1000$, $1 \leq S \leq 10^9$), the number of rows and columns of the map, and the number of water cells the solution travels.
The following $N$ lines contain a map of Sjön-Sjøn. Each line consists of $M$ characters, each one of which is either “#”, “<”, “>”, “^” or “v”. These represent land, water flowing west, water flowing east, water flowing north and water flowing south respectively. Lines are given from northernmost to southernmost, and characters within a line are given from westernmost to easternmost.
Output
Output the minimum number of cells that need to have cleaning solution poured into them in order to clean all of sjön Sjön, or “impossible” if it’s impossible to clean all of sjön Sjön no matter how many cells receive cleaning solution.
Scoring
|
Group |
Points |
Constraints |
Satisfied by Sample Input(s) |
|
$1$ |
$15$ |
$N = 3$ |
$1$ |
|
$2$ |
$15$ |
$S = 10^9$ |
$4$ |
|
$3$ |
$20$ |
There is no grid cell where the water flows north ('^') |
$1$, $2$ and $5$ |
|
$4$ |
$20$ |
$N,M \leq 80$ |
All sample inputs |
|
$5$ |
$30$ |
No further constraints |
All sample inputs |
Sample Description
![\includegraphics[width=0.3\textwidth ]{img/sample.jpg}](/problems/lthchallenge22.sjonsjoncleanup/file/statement/en/img-0002.jpg)
| Sample Input 1 | Sample Output 1 |
|---|---|
3 11 3 ########### #>>>><<#v<# ########### |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 6 3 ###### ##v<v# #v<#v# #v#v<# #><<## ###### |
5 |
| Sample Input 3 | Sample Output 3 |
|---|---|
17 14 5 ############## ###########v^# ########v<<>^# ########>v^<## #######>^>^^## ######>^v<<<## #####>>vvv<<<# ####>v>v>v><<# ####v>^>^<<<## ###vv><<<<<### ###v>^#<v<#### ###>v##^><#### ##>v>>>^<##### ##^>>><<<##### #>>>v^<<###### #^<<>>>>###### ############## |
22 |
| Sample Input 4 | Sample Output 4 |
|---|---|
17 14 1000000000 ############## ###########v^# ########v<<>^# ########>v^<## #######>^>^^## ######>^v<<<## #####>>vvv<<<# ####>v>v>v><<# ####v>^>^<<<## ###vv><<<<<### ###v>^#<v<#### ###>v##^><#### ##>v>>>^<##### ##^>>><<<##### #>>>v^<<###### #^<<>>>>###### ############## |
18 |
| Sample Input 5 | Sample Output 5 |
|---|---|
5 7 2 ####### ##>>vv# #v#v<v# #>>><<# ####### |
impossible |
