Swan Lake
Time limit1sMemory limit256 MB
Given a grid where ice melts by BFS layers each day, find the minimum number of days until two marked swan cells become connected through water.
- Level
Hard8 of 10
- Topics
- Binary search, BFS, Matrix
- Solved
- No attempts yet
Problem
Two swans live on a rectangular lake. Part of the lake is frozen, so at first the swans may not be able to reach each other.
The lake is an R by C grid. Each cell is either water or ice.
Each day, every ice cell that is horizontally or vertically adjacent to water melts into water. Diagonal contact does not count.
The diagram below shows three stages of the melting process.
...XXXXXX..XX.XXX ....XXXX.......XX .....XX..........
....XXXXXXXXX.XXX .....XXXX..X..... ......X..........
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X.....
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX....
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX....
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............
..XXXXX...XXX.... ....XX.....X..... .................
....XXXXX.XXX.... .....XX....X..... .................
initial day 1 day 2
A swan can move only through water cells, and only to a horizontally or vertically adjacent water cell. Diagonal movement is not allowed.
Determine the minimum number of days that must pass before the two swans can meet.
Input
The first line contains integers R and C. (1 ≤ R, C ≤ 1500)
Each of the next R lines contains one string of length C. . means water, X means ice, and L means a cell containing a swan. A cell containing a swan is treated as water.
Output
Print the minimum number of days needed until the two swans can meet.