|
题 沿网格线从 A(-3,-2) 到 B(5,2),途中要经过 P(-1,1) 或 Q(-2,2) 的最短路径有几条?
解 一般来说,设 S(p,q),T(m,n)(其中 m≥p ,n≥q)是坐标平面上两点。
沿网格线从 S(p,q) 到 T(m,n) 的最短路径共有 C(m-p+n-q,m-p) 条。
在本题中,沿网格线从 A(-3,-2) 到 P(-1,1) 的最短路径有 C(-1+3+1+2,-1+3)=C(5,2) 条。
沿网格线从 P(-1,1) 到 B(5,2) 的最短路径有 C(5+1+2-1,5+1)=C(7,6) 条。
所以,从 A 经过 P 再到 B 的最短路径有 C(5,2)×C(7,6) = 10×7 = 70 条。
沿网格线从 A(-3,-2) 到 Q(-2,2) 的最短路径有 C(-2+3+2+2,-2+3)=C(5,1) 条。
沿网格线从 Q(-2,2) 到 B(5,2) 的最短路径有 C(5+2+2-2,5+2)=C(7,7) 条。
所以,从 A 经过 Q 再到 B 的最短路径有 C(5,1)×C(7,7) = 5×1 = 5 条。
总之,从 A 到 B ,途中经过 P 或 Q 的最短路径共有 70+5 = 75 条。 |
|