从a到b一共4条东西的路，6条南北的路
画出图形就是一个矩形，被切割成了3*5块，a和b各自占据一个顶点，a在左下角，b在右上角
问，不绕路的情况下，a到b一共几种走法

给出完整程序最好了~

深度搜索就解决了   广度搜也可以 不过只能找到一条最短步数的路径  

哦，现在去看看深度搜索

很简单的递归：

进入递归体后，判断是否越界，若越界则直接返回。
未越界，则判断是否已达到目的地，若达到则输出路径。
皆非，则开始递归
首先向右一步，进入递归。
然后向上一步，进入递归。
over

由于问题的特殊性，不必考虑其它方向的递归。

收到的鲜花

• xdh0817 于 2012-02-16 22:08 送鲜花  5朵   附言：~

我也想知道

这样的走法，每条都是最短路径，其长度就是矩形长宽的和。
由南北路和东西路相交出若干个交点，交点a在左下角，交点b在右上角。要想不绕路，位于每个交点的行进方向只能要么向上，要么向右。
所以，要到达某个交点的方法即是到达它相邻左边交点与到达它相邻下边交点的方法之和。起始点a的走法为1。
这是典型的DP题。

学习了 杨大哥  真不好意思我又写了个回溯。。。。

呵呵，这大概是个思维习惯。写了段示例

#include<stdio.h>
#include<malloc.h>

int path_count(int a, int b)
{
    int i, *p;
    if(a == 1 || b == 1) return 1;
    p = (int *)malloc(a * sizeof(int));
    for(i = 0; i < a; i++) p[i] = i + 1;
    for(b -= 2; b--;)
    for(i = 1; i < a; i++) p[i] += p[i - 1];
    i = p[a - 1];
    free(p);
    return i;
}

int main()
{
    int a, b; //a, b为横纵路线数，哪个是横，哪个是纵无所谓
    scanf("%d %d", &a, &b);
    printf("%d\n", path_count(a, b)); //注意数据范围
    return 0;
}

收到的鲜花

• xdh0817 于 2012-02-16 22:08 送鲜花  5朵   附言：好文章

这个不要遍历,可以直接算出来的吧

假设向右走a步，向上走b步，可以想象成把向右走的这a步分散在b步的空隙之中，所以等价于
x1+x2+...xb+1=a (x>=0)的解数目，即C(a+b,a)