Move only right or down, and count the different routes across a map with walls.
What to build
A two-dimensional table that counts the routes from the top-left square to the bottom-right square.
Requirements
- Each move goes one square right or one square down.
- A route cannot use a square marked
#. - Print 0 if the start or the end is a wall.
Input
The first line has R and C. Each of the next R lines has C characters, . or #.
Output
The number of routes.
Constraints
1 ≤ R, C ≤ 12.
Example
Input:
3 3
...
...
...
Output:
6
Why it works
Every route into a square comes from above or from the left, and no route comes from both, so the two counts add. Filling row by row means both values are ready when they are needed.
Examples
Example 1 · Input
3 3 ... ... ...
Expected output
6
Example 2 · Input
3 3 ... .#. ...
Expected output
2
Hints
Hint 1
A square can only be reached from the square above it or the square to its left.
Hint 2
So `ways[r][c]` is the sum of those two, and it is 0 on a wall.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int R, C;
char grid[12][14];
long long ways[12][12];
scanf("%d %d", &R, &C);
for (int r = 0; r < R; r++) scanf("%13s", grid[r]);
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] == '#') ways[r][c] = 0;
else if (r == 0 && c == 0) ways[r][c] = 1;
else ways[r][c] = (r > 0 ? ways[r - 1][c] : 0) + (c > 0 ? ways[r][c - 1] : 0);
}
}
printf("%lld\n", ways[R - 1][C - 1]);
return 0;
}