路线与染色问题

下图是一个 3×3 的方格网格，从左上角 A 点到右下角 B 点，每次只能向右或向下移动一格。网格中有两个红色格子，分别是 C（第2行第2列）和 D（第3行第2列）。现在要求：所有从 A 到 B 的路径中，必须恰好经过其中一个红色格子（要么经过 C 且不经过 D，要么经过 D 且不经过 C）。请问满足条件的路径共有多少条？

先找出所有从 A 到 B 的路径共有多少条（6条）。然后按“经过 C 不经过 D”和“经过 D 不经过 C”两类分别计算。注意：“经过 C”的路径里有一部分也经过了 D，需要排除。用标数法或组合数计算各段路径数，最后用加法原理合并。

1. 明确网格大小：A(1,1)，B(3,3)。需要向右走2步，向下走2步，共4步。所有路径数 = 从4步里选2步向右，即 $C_4^2=6$ 条。 2. 先算“经过 C 但不经过 D”的路径： - 从 A 到 C：C 在(2,2)，需要向右1步、向下1步，共2步。选1步向右，路径数 = $C_2^1=2$ 条。 - 从 C 到 B：C 到 B 需要向右1步、向下1步，共2步。但要求不经过 D，所以从 C 出发不能向下走（因为向下会到 D），只能向右走到(2,3)，再从(2,3)向下到 B。这段路径只有1种走法（先右再下）。 - 所以“经过 C 不经过 D”的路径数 = 2 × 1 = 2 条。 3. 再算“经过 D 但不经过 C”的路径： - 从 A 到 D：D 在(3,2)，需要向右1步、向下2步，共3步。总路径数 = $C_3^1=3$ 条。 - 其中有一部分路径会经过 C（即先到 C 再到 D）。从 A 到 C 有2种，C 到 D 只有1种（向下），所以“经过 C 再到 D”的路径有 2×1=2 条。 - 因此“从 A 到 D 且不经过 C”的路径 = 3 - 2 = 1 条。 - 从 D 到 B：D 到 B 只需要向右1步，只有1种走法。 - 所以“经过 D 不经过 C”的路径数 = 1 × 1 = 1 条。 4. 总路径数 = 2 + 1 = 3 条。 5. 验证：所有6条路径中，不经过任何红色格子的有1条（RRDD），经过两个红色的有2条（RDDR、DRDR），只经过一个红色的正好是剩下的3条（RDRD、DRRD、DDRR）。答案正确。

3 条

遇到“恰好经过一个特殊点”的问题，先分两类（经过A不经过B、经过B不经过A），每一类用“分步乘法”计算路径数。注意排除同时经过两个特殊点的情况，可以用总数减去重复部分，或者直接分类讨论排除。