05年复赛第二题 城市的道路

05年复赛第二题 城市的道路

某城市的道路呈整齐的方格网状，东西走向的道路为M条，南北走向的道路为N条，某人住在城市的西南角A处，每天骑自行车到东北角的B处上班。为了顺便观光市容，他经常改变行车路线，他的原则是每次行车只能向北或向东,总是朝着单位的方向,最后一定到达单位.这样从A点到B点有多少种走法?
由键盘输入M和N的值(1<=20,且为整数),在屏幕上输出显示走法总数.>
例如:左图为东西向有5条,南北向有9条路,从A点(西南角)走向B点(东北角)共有495种走法.
输入样例:(键盘)
5,9
输出样例:(屏幕)
495

分析：
　　本题使用二维数组进行道路的模拟，每个结点表示从（0，0）点到本结点的路线总数。
1----1

1----1
| |
| |
| |
1----2

1----1
| |
| |
| |
1----2
| |
| |
| |
1----3

1----1----1
| | |
| | |
| | |
1----2----3
| | |
| | |
| | |
1----3----6

根据此分析，路线数＝左侧路线数＋上方路线数，由此迭代解决此问题。

C代码：

#include < stdio.h >
#include < stdlib.h >
#include < math.h >
#include < string.h >

int main(int argc, char **argv)
{
    int m, n, i, j;
    long long **matrix;
    scanf("%d, %d", &m, &n);
    matrix = malloc(sizeof(long long *) * m);
    for (i = 0; i < m; i++) {
        matrix[i] = (long long *)malloc(sizeof(long long) * n);
    }
    for (i = 0; i < m; i++) {
        matrix[i][0] = 1;
    }
    for (j = 0; j < n; j++) {
        matrix[0][j] = 1;
    }

    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
            matrix[i][j] = matrix[i-1][j] + matrix[i][j-1];
        }
    }

    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            printf("%lld\t", matrix[i][j]);
        }
        printf("\n");
    }
    printf("%lld\n", matrix[m-1][n-1]);

    for (i = 0; i < m; i++) {
        free(matrix[i]);
    }
    free(matrix);

    return 0;
}