#USACOC2214C. Walking Home
Walking Home
Description
Bessie the cow is trying to walk from her favorite pasture back to her barn.
The pasture and farm are on an grid, with herpasture in the top-left corner and the barn in the bottom-right corner. Bessiewants to get home as soon as possible, so she will only walk down and to theright. There are haybales in some locations that Bessie cannot walk through; shemust walk around them.
Bessie is feeling a little tired today, so she wants to change the direction shewalks at most times .
How many distinct paths can Bessie walk from her favorite pasture to the barn?Two paths are distinct if Bessie walks in a square in one path but not in theother.
Input Format
The input for each test case contains sub-test cases, each describing adifferent farm and each of which must be answered correctly to pass the fulltest case. The first line of input contains . Each ofthe sub-test cases follow.
Each sub-test case starts with a line containing and .
The next lines each contain a string of characters. Each character iseither if it is empty or if it has a haybale. It isguaranteed the top-left and bottom-right corners of the farm will not containhaybales.
Output Format
Output lines, the -th line containing the number of distinct paths Bessiecan take in the -th sub-test case.
7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...
7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...
Scoring
- Test case 2 satisfies .
- Test cases 3-5 satisfy .
- Test cases 6-10 satisfy .
Problem Credit
Problem credits: Nick Wu