Smooth Sailing (Hard Version)

1920F23000· legendary gm5s1024 MB⌨ stdin/stdout

#binary search #data structures #dsu #geometry #graphs #trees

Examples

Sample 1of 4

Input

9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7

Output

3
0
3

Sample 2of 4

Input

3 3 5
..v
.#.
...
1 2
1 3
2 3
2 1
3 2

Output

Sample 3of 4

Input

14 13 5
.............
.............
.............
...vvvvvvv...
...v.....v...
...v.###.v...
...v.#.#.v...
...v..v..v...
...v..v..v...
....v...v....
.....vvv.....
.............
.............
.............
1 1
7 7
5 6
4 10
13 6

Output

Sample 4of 4

Input

10 11 4
...........
..#######..
..#..#..#..
..#.....#..
..#..v..#..
..#.###.#..
..#.#.#.#..
..#...#.#..
..#####.#..
...........
7 6
3 7
6 8
1 1

Output

1920F2.cpp

loading editor…

Ln 11·137 BGNU C++20 (64)

loading graph engine…