Graph problem?

Question

Mathematics

Update: below is the full condition of the problem
Again I was solving problems on acm, and at the regional training I came across such a problem. It takes a long time to write the text of the task itself, since there is a lot of water. Therefore, I simplify as much as possible.
Here is the gist:
There is a table RxS, 2<=R,S<=10. How many ways are there to get from the top left cell to the bottom right cell if the cells must not be repeated along the way?
When we deal with this, there is another complication - cells are set through which it is impossible to pass.
Movement - up, down, left, right.
In the condition, the cells through which it is possible to pass are given by the dot symbol ".", and the closed ones - by the lattice "#"
Examples
…
.#.
Answer: 1 (there is only one way, it is clearly visible)
…
…
...
Answer: 12 (well, it's not so obvious here, but you can calculate it manually)
So, I wrote my own recursive method, but this is a simple enumeration, which, with R, S > 4, has been thinking for a very long time. I've read the books and haven't found anything accurate.
This is the task that torments me. Help!
Full condition of the problem:
Plumber Petya was hired to lay a water pipe between two points of the city. The map of the city can be
represented as a rectangle of size RxS, which consists of square cells. In some cells, a pipe cannot be placed.
Petya must use a pipe to connect the place located above the upper left cell and the place under the lower right cell.
Petya can either leave each admissible cell empty or place a pipe fragment of one of the following 6 types into it.

Find the number of ways Petya can build a continuous pipe that connects the indicated two points by placing the fragments he has in the cells.
Output the number of ways modulo 10007
Input:
The first line contains integers R and S (2 <= R,S <= 10), the number of rows and columns on the city map. Each of the following R lines contains exactly S characters: "." — if the cell is suitable for placing the pipe, and "#" if not.
Output:
Number of ways modulo 10007
Examples
Input
2 3
…
.#.
Output
1
Input
3 3
…
…
…
Output
12

Answer 1

Vryatli my opinion is the most correct, but since no one else has unsubscribed, let me suggest the following:
By creating a recursion "on the forehead" we kind of go deep into the depths. A rough estimate says that the order will be: 4^(R+S), since there are at least R+S moves in one path, each move generates 4 options for further movement.
You can use something like breadth-first search / Dynamic Programming: assign to each cell the number of paths leading from the upper left edge to it, and fill it in from near to far. Base: 1 possible path from the first vertex to itself. Transition: if a cell is surrounded by cells with values ​​a1, a2, a3, a4 (not all of them can be determined, we temporarily set them to zero), then the value of the cell is their minimum min(a1, a2, a3, a4). We finish when we get the value for the lower right. Bypassing all cells will require R * S steps, the complexity of the algorithm is the same.