主题:联赛试题
设有一个N*M(l<=N<=50,l<=M<=50)的街道(如图一):(40%)
北
5┌─┬─┬─┬─┬─┬─┬─┬─┐B(9,5)
│ │ │ │ │ │ │ │ │
4├─┼─┼─┼─┼─┼─┼─┼─┤
│ │*│*│*│*│*│*│ │ 东
西3├─┼─┼─┼─┼─┼─┼─┼─┤
│ │*│*│*│*│*│*│ │
2├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ │ │
1└─┴─┴─┴─┴─┴─┴─┴─┘
1 2 3 4 5 6 7 8 9
A(1,1) 南
(图一)
规定行人从A(1,1)出发,在街道上只能向东或北方向行走。
图二为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对顶点坐标(X1,y1),
(X2,Y2),然后求出此种情况下所有从A出发到达B的路径的条数。
北
5┌─┬─┬─┬─┬─┬─┬─┬─┐B(9,5)
│ │ │ │ │ │ │ │ │
4├─┼─┼─┼─┼─┼─┼─┼─┤
│ │*│*│*│*│*│*│ │ 东
西3├─┼─┼─┼─┼─┼─┼─┼─┤
│ │*│*│*│*│*│*│ │
2├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ │ │
1└─┴─┴─┴─┴─┴─┴─┴─┘
1 2 3 4 5 6 7 8 9
A(1,1) 南
(图一)
规定行人从A(1,1)出发,在街道上只能向东或北方向行走。
图二为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对顶点坐标(X1,y1),
(X2,Y2),然后求出此种情况下所有从A出发到达B的路径的条数。