Loading...
Loading...
Loading...
The college corridor floor is a grid of r rows and c columns of tiles. Some tiles have wet paint, and nobody may step on them. A dry tile is shown as . and a wet tile as #.
Rohan stands on the top-left tile and must reach the bottom-right tile. Each step moves him one tile to the right or one tile down, and he may only step on dry tiles.
Print the number of different routes, modulo 10^9 + 7. If the start or the end tile is wet, or no route exists, print 0.
. or #.. (dry) or # (wet).Example 1
Input
3 3 ... .#. ...
Output
2
The wet centre tile leaves only the two routes along the edges.
Example 2
Input
3 4 .... .#.. ....
Output
4
Of the 10 routes in an empty 3 × 4 grid, the 6 that pass over the wet tile are removed, leaving 4.
Try the problem first. Open one hint at a time.
As with an empty grid, the routes to a tile come from the tile above and the tile on its left.
A wet tile has zero routes into it, so it adds nothing to the tiles after it.
The start tile has one route if it is dry and zero if it is wet.
For the top row and the left column, add only the neighbour that exists. Do not set them to 1 blindly.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor