The Problem: given a grid of size (M+1)x(N+1),
A(0,0)+--+--+--+--+--+--+ (0,6) N=6
| | | | | | |
+--+--+--+--+--+--+
| | | | | | |
+--+--+--+--+--+--+
| | | | | | |
+--+--+--+--+--+--+
| | | | | | |
+--+--+--+--+--+--+
| | | | | | |
+--+--+--+--+--+--+
| | | | | | |
+--+--+--+--+--+--+
| | | | | | |
+--+--+--+--+--+--+
| | | | | | |
+--+--+--+--+--+--+
| | | | | | |
+--+--+--+--+--+--+ B(9,6)
M = 9 (9,0)
the question is how to get the number of shortest paths from point A (0,0)
to point B (M,N). A shortest path from A to B consists of only edges of
left to right, or up to down, i.e. with length M+N.
A very straightforward program will use recursive call:
//row: 0..M
//col: 0..N
//pathcount returns the number of shortest paths from (0,0) to (row, col)
int pathcount(int row, int col)
{
if (row==0 && col==0)
return 0;
else if (row==0)
return 1;
else if (col==0)
return 1;
else
return pathcount(row-1,col)+pathcount(row,col-1);
}
A more elaborated implementation will do the calculation in a bottom up way:
template < size_t M, size_t N>
int pathcount()
{
int i, j;
int pc[M+1][N+1];
pc[0][0] = 0;
for(i=1; i <= N; i++)
pc[0][i]=1;
for(i=1; i <= M; i++)
pc[i][0]=1;
for(i=1; i <= M; i++) //rows
for(int j=i; j <= N; j++) //cols
{
pc[i][j] = pc[i-1][j]+pc[i][j-1];
if ( j <= M ) // note that i <= N
pc[j][i] = pc[i][j];
}
return pc[M][N];
}
This implementation actually calculates the number of shortest paths from (0,0) to any (i,j) where i<=M and j<=N. Therefore, pc[M][N] will be the number of shortest paths from (0,0) to (M,N).