University of Toronto ACM-ICPC Tryouts 2013
This evening, Alice and Bob have decided to simply go out on a nice walk
together. On the way, they'll traverse
A given sidewalk can be modelled as a two-dimensional grid of cells,
with .
), or is blocked by the
neighbourhood dog's droppings (#
). Alice and Bob will be walking
Southwards along it, independently of one another, but both at a rate of
exactly one row per second. Needless to say, they'll never walk through
cells containing droppings, nor can they ever occupy the same cell as
one another. Each of them can start in any cell on row 1, and each
second, will move down by a cell, as well as optionally left or right by
a cell. In other words, if Alice or Bob is in cell
Along the way, whenever Alice and Bob find themselves side-by-side (in
other words, in cells
Input Specification
Line 1: 1 integer,
For each sidewalk:
Line 1: 2 integers,
Next
Output Specification
For each sidewalk, output 1 integer, the maximal number of seconds Alice
and Bob can spend holding hands, or the string Detour
if they can't
both make it to the end.
Sample Input
2
5 5
#....
..##.
.#...
#.#..
....#
2 4
.##.
..##
Sample Output
4
Detour
Explanation of Sample
On the first sidewalk, Bob can ask Alice to walk through cells
However, there's no way for both Alice and Bob to navigate the second
sidewalk. They must start in cells
Comments