A small chip is composed of a grid of contacts (marked as dots). Some are already connected (marked as line segments). Connectors are always only between adjacent contacts, horizontally or vertically. We want to connect S and R with a continuous sequence of connectors, which do not touch any already connected contacts.
一个小芯片由一个触点网格（标记为点）组成。其中一些触点已经连接（标记为线段）。连接器总是仅在相邻触点之间水平或垂直连接。我们希望用一连串的连接器将 S 和 R 连接起来，且这些连接器不能接触任何已连接的触点。
Question: 问题:
How many different ways are there to connect S and R with the least possible number of connectors?
用最少的连接器将 S 和 R 连接起来，有多少种不同的连接方式？
A. 5
B. 13
C. 15
D. 16
Explanation 解释
The correct answer is: 15
正确答案是：15
It is not difficult to find some shortest path (sequence of connectors). You can imagine a wave spreading over the board, one contact at a time, starting at S and moving toward R. When the wave reaches a contact, it certainly took the least possible number of connectors (“steps” of the wave).
要找到一些最短路径（连接器序列）并不难。你可以想象一个波浪在电路板上逐个接触点地扩散开来，从 S 点开始向 R 点移动。当波浪到达某个接触点时，它肯定已经经过了最少数量的连接器（波浪的“步数”）。
The table shows the wave midway through filling in. The numbers show the order in which the wave reached them, and the blacked out cells indicate the connectors we cannot connect to. They are also the length of the shortest path to the respective contact. The highest numbers are the current edge of the wave.
该表展示了波形在填充过程中的中间状态。数字表示波形到达各单元格的顺序，黑色单元格表示无法连接的连接器，它们也是到达相应触点的最短路径长度。最大的数字表示当前波形的前沿。
But if you try to find all the shortest paths, you can easily get lost. Luckily, you do not really need to, you are just interested in the number of paths. So how to break this task down to some smaller pieces?
但如果你试图找出所有最短路径，很容易迷失方向。幸运的是，你其实并不需要这么做，你只是对路径的数量感兴趣。那么如何将这个任务分解成一些更小的部分呢？
Realize this: A shortest path to any given contact must go through one of the adjacent contacts, which is exactly one connector closer to the start. If there are more such contacts, any of them can be used. So if you want to know the number of possibilities, you need to sum the possibilities to get to these adjacent contacts. The number of shortest paths to a certain contact is the sum of the numbers of the shortest paths to the adjacent contacts which are one connector closer to the start.
要明白这一点：到达任何给定接触点的最短路径必须经过其中一个相邻接触点，而该相邻接触点恰好比起始点更近一个连接器。如果有多个这样的接触点，那么其中任何一个都可以使用。所以，如果您想知道可能性的数量，就需要将到达这些相邻接触点的可能性相加。到达某个接触点的最短路径数量，就是到达比起始点更近一个连接器的相邻接触点的最短路径数量之和。
This allows you to follow a procedure, which will reliably give you the final number of shortest paths. You can proceed similarly as with finding the shortest path, filling in the table like a wave. Start at S. The contacts next to it can be reached in only one way. Then add the next contacts along the wave edge and always sum up the neighbour numbers from the previous step.
这使您能够遵循一个程序，该程序能可靠地得出最短路径的最终数量。您可以像寻找最短路径那样进行操作，像波浪一样逐步填满表格。从 S 开始。与它相邻的节点只能通过一种方式到达。然后沿着波浪边缘添加下一个节点，并始终将前一步中相邻节点的数量相加。
The resulting table looks like this, where we have also shown the order in which the cells are filled in by way of the table on the right, which is the completely filled in “shortest path” table discussed above:
最终得到的表格如下所示，我们还在右侧的表格中展示了单元格的填充顺序，该表格即为上文所讨论的已完全填好的“最短路径”表：
Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓
欢迎咨询【Bebras专业辅导课程】
（Bebras每日一练部分展示）
