Walk and jump P87501
Given an n × m map with obstacles, in how many ways can we go from the upper-left corner to the lower-right corner? We can only walk (move to the cell immediately to the right or below), or jump (move to the cell two positions to the right or below, but only by jumping an obstacle). We can never visit any obstacle.
Input
Input consists of several cases. Every case begins with n and m, followed by n rows with c characters each. The cells with an obstacle have an ‘X’, and the empty cells a period. The initial and final cells are always empty. Assume that both n and m are between 2 and 100.
Output
For every case, print the number of ways to go from the beginning to the end, as explained above. Since this number can be very large, make the computations modulo 108 + 7.
Input
2 3 ... ... 3 6 .X...X .XX... .X.... 10 35 ................................... ................................... ................................... ................................... ................................... ................................... ................................... ................................... ................................... ...................................
Output
3 7 63921960
- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++