Problem D
Robots on a Grid

You have recently made a grid traversing robot that can find its way from the top left corner of a grid to the bottom right corner. However, you had forgotten all your AI programming skills, so you only programmed your robot to go rightwards and downwards (that’s after all where the goal is). You have placed your robot on a grid with some obstacles, and you sit and observe. However, after a while you get tired of observing it getting stuck, and ask yourself “How many paths are there from the start position to the goal position?”, and “If there are none, could the robot have made it to the goal if it could walk upwards and leftwards?”
So you decide to write a program that, given a grid of size
Input
On the first line is one integer,
Output
Output one line with the number of different paths starting
in
Sample Input 1 | Sample Output 1 |
---|---|
5 ..... #..#. #..#. ...#. ..... |
6 |
Sample Input 2 | Sample Output 2 |
---|---|
7 ......# ####... .#..... .#...#. .#..... .#..### .#..... |
THE GAME IS A LIE |