Background
I have constructed a simple obstacle course by placing boxes in a rectangular room. Now I want to count the number of essentially different ways in which it can be solved. I need you to write me a program for that.
Input
Your input is a non-empty rectangular array of the characters .#
.
The dots .
are empty space, and the #
are obstacles.
A path through the obstacle course begins at the top left corner and ends at the bottom right corner, and goes only right or down.
Also, a valid path cannot go through an obstacle.
Here are some examples drawn with +
-characters:
Valid path Invalid path Invalid path Invalid path
++........ ++........ +++++..... ..+.......
.++++++#.. .+.....#.. ....+++#++ ..++...#..
......+#.. .+.++++#.. .......#.+ ...+++.#..
....#.++++ .+++#.++++ ....#....+ ....#+....
Two paths are essentially similar1 if one can be transformed into the other by moving one +
at a time.
The intermediate paths must also be valid, so you can't bend a path over an obstacle.
For example, the first two paths here are essentially similar, but the third is essentially different from them, since it can't be wiggled over the two obstacles:
++........ +......... +++++++++.
.+++++.#.. ++.....#.. .......#+.
.....+.#.. .++++++#.. .......#++
....#+++++ ....#.++++ ....#....+
Output
Your output is the number of essentially different paths through the obstacle course. In other words, if all the valid paths are divided into classes of essentially similar paths, the output is the number of classes. Note that this number may be 0, if there are no valid paths.
Rules and scoring
You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. There are no time bounds, except that you should evaluate your program on every test case before submitting it.
Test cases
....
....
.... => 1
...#
....
...# => 0
#..#
..#.
.... => 0
......
......
..##..
......
...... => 2
......
...#..
......
..#...
#..... => 3
......
..#...
......
....#.
#..... => 4
.......
##.....
....###
...#...
..##.#.
#....#.
..#.... => 0
......#.
..##....
...#....
.......#
....#...
.##...#.
....#...
##...... => 7
.........
.#.#.#.#.
.........
#.#...#.#
.........
.#.#.#.#.
......... => 17
..........
.#........
..........
.....#....
#.........
........#.
......#...
.......... => 10
.........
.#.......
.........
...#.....
.........
.....#...
.........
.......#.
......... => 16
1 The correct technical term is "homotopic".
+
at a time"? Does this imply that essentially similar paths must be the same length? \$\endgroup\$+
" I essentially mean that one corner of the path is inverted into a corner of the opposite direction. \$\endgroup\$