Jumpers and Commanders
Time Limit: 3 Seconds Memory Limit: 131072 KB
This year, Milad won the cup of “Jumpers and Commanders” AI Contest. His smart jumper agent (the agent that he has programmed) did all the jumping tasks correctly.
A jumper agent is a robot that automatically and continuously jumps 1 unit (column) forward in constant time intervals from the time it is turned on. We call this kind of jumps “Forward Jump”. These jumpers can be programmed to jump upward or downward by special commands “up” and “down” respectively (1 unit per command). Special commands can only be executed between two forward jumps, i.e. after each forward jump, the agent checks its command list and executes (if any) “up” and “down” commands, and then performs the next forward jump.
A jumping task is defined as follow:
· There is a n × m (n rows and m columns) grid map with 2 <= n <= 50, 2 <= m <= 10000.
· Some grid cells are blocked and no jumper can jump there. Also jumpers cannot jump over a blocked cell.
· A jumper should be placed on any of the cells in the first column of the map (contestant can choose any of the cells in the first column) and begin jumping to the last column without any jumps on blocked cells (It is clear that the number of forward jump intervals is equal to the number of map columns).
· Total number of commands in all command lists must be minimum.
Each jumper has a commander IC in its circuit. This IC is responsible for generating special commands (up and down) list. It is a programmable IC and must be programed by contestants in a way that it produces the correct special command list in each forward jump interval according to the map (it is also possible to generate an empty command list for a specific interval).
An Example of a Jumper and Its Commander (right table) for a Jumping Task (left table)
Input
The first line of the input contains an integer t, number of test cases.
In the first line of each test case, there are two integers n and m, denoting number of rows and columns respectively, followed by n strings. The ith string specifies the state of all cells of the ith row. Strings are consist of two kind of characters; ‘.’ for empty cell and ‘#’ for blocked cells. It is guaranteed that there is at least one way to start from first column and end with the last column.
Output
For each test, print a line containing the minimum total number of up and down commands, the commander generates, if Milad places his agent on the map.
Sample Input
3 3 5 .#... ...#. .###. 5 10 #....#.... ..##.#.#.. #....#...# ..##.#.#.# #..#...#.. 3 5 ##### ..... #####
Sample Output
1 6 0Submit