回 帖 发 新 帖 刷新版面

主题:一道题适合高中生的题

三、设有一个N*M(1<=N<=50,1<= M<=50)的街道
         (如下图)
                         北
                                    B(9,5)
                     西     东 
                                                     图一
                                         123456789
                           A(1,1)
                           南
  北 
 5┌─┬─┬─┬─┬─┬─┬─┬─┐B(9,5)
  │ │ │ │ │ │ │ │ │
 4├─┼─┼─┼─┼─┼─┼─┼─┤
  │ │*│*│*│*│*│*│ │ 东
西3├─┼─┼─┼─┼─┼─┼─┼─┤
  │ │*│*│大│*│*│*│ │
 2├─┼─┼─┼─┼─┼─┼─┼─┤
  │ │ │ │ │ │ │ │ │
 1└─┴─┴─┴─┴─┴─┴─┴─┘
  1 2 3 4 5 6 7 8 9
 A(1,1)   南
  (图一)
  规定:行人从A出发.在街道上只能向东或北
          方向行走。  如下图N=3,M=3的街道图,
           从A出发到达B共有6条可供行走的路径
    1.A-A1-A2-A5-B
    2 A一A1-A4-A5-B
  3.A一A1- A4—A7-B
 4.A一A3-A4—A5—B
 5.A-A3-A4—A7-B
    6.A-A3- A6- A7- B 
四. 在N*M的街道中,设置一个矩形障碍区域
       (包括围住该区域的的街道)不让行人退行,
         如图一中用“*”表示的部分。
       此矩形障碍区域用2对顶点坐标给出,图一
        中的2对顶点坐标为:(2,2),(8,4)
        此时从A出发到达B的路径仅有两条。
    程序要求:
    任务一:给出N,M后,求出所有从A出发到达B
         的路径的条数。
    任务二:给出N,M,同时再给出此街道中的矩
         形障碍区域的2对
         顶点坐标(X2,Y2),然后求出此种情况下所
         有从A出发到达B的路径的条数。

回复列表 (共1个回复)

沙发

唉...状态方程:
f[x,y]:=f[x,y-1]+f[x-1,y];
PS:f[x,y]是从A到(x,y)的路径数.
   若(x,y)是障碍则f[x,y]=0.

我来回复

您尚未登录,请登录后再回复。点此登录或注册