程序员的算法趣题Q34: 会有几次命中注定的相遇(2)

0. 前情概要

参见：Q34: 会有几次命中注定的相遇

1. 分析

如上所述，在满足相遇的两种条件之一后即提前退出会导致大量的路径（满足相遇条件后的路径分岔）被漏算了。正确的做法是只要不出界，就必须一直走到底。由此可以看出在之前的错误的解答中的以下4个return的条件（如下图所示）中，第2个、第3个、第4个其实都是错的，都是不需要的。

第3、4个的错的原因已经解释了，其实不能提前退出，每条路径都走到底再做判断。

其中第2个是错误的原因还需要再追加一点解释。第2个return是基于这样的考虑：（在错解中认为）一旦找到满足条件的就应该提前退出，而如果两者都已经擦肩而过（满足了“manX > womanX and manY > womanY”之后就不可能再相遇了）且还没有满足条件的话就不必继续搜索下去了。而现在要求不管是否已经满足条件，都必须每条路径走到底，这个return自然就不再需要了。因为任何一对路径不管是否满足相遇的条件下，最后一段都必然是满足“manX > womanX and manY > womanY”条件的。

进一步如以下代码所示统计条件和退出条件做了一些调整优化。

首先meet递增改为针对X坐标和Y坐标分别统计。X和Y坐标同时相同（即题设中的相互解除状态）无非就是统计成加2而已（反正现在不比提前退出）。这样做的好处是统一了两种相遇的情况的统计。

此外，最终判断是否满足相遇条件是用(meet>=2)，有人可能会有疑惑会有meet>2的情况吗？是的。因为统计是每走一步都统计的，考虑两者在某一点相遇后两者继续朝相反方向走，那两人的某一个坐标必定继续保持一致，因此会导致meet一直增加直到到达边界不得不转向为止。

2. 代码

# -*- coding: utf-8 -*-
"""
Created on Sun Sep 19 08:24:18 2021

@author: chenxy
"""
import sys
import time
import datetime
import random
from   typing import List
from   collections import deque
import itertools as it
import numpy as np

N = 6
M = 6
total_count = 0

def f(manX, manY, womanX, womanY, meet):
    # print(manX, manY, womanX, womanY, meet)
    global total_count

    if manX > N or manY > M or womanX < 0 or womanY < 0:
        return # Cross the boundary
    # if manX > womanX and manY > womanY:
        # return # Missed forever

    # if manX == N and manY == M and womanX == 0 and womanY == 0:
    # Can be simplied as below:
    if manX == N and manY == M:
        # Both people reach their target respectively, then do the judgement
        if meet >= 2:
            total_count += 1
        return    
    
    if manX == womanX:
        meet += 1
    if manY == womanY:
        meet += 1        
        
    # Four possible move combination of two people
    f(manX+1, manY, womanX-1, womanY, meet)
    f(manX+1, manY, womanX, womanY-1, meet)
    f(manX, manY+1, womanX-1, womanY, meet)
    f(manX, manY+1, womanX, womanY-1, meet)

    return

tStart  = time.perf_counter()
f(0, 0, N, M, 0)
tCost  = time.perf_counter() - tStart

print('total_count = {0}, tCost = {1:6.3f}(sec)'.format(total_count,tCost))  

运行结果：total_count = 527552, tCost = 1.438(sec)

3. 后记

在很多的路径遍历搜索问题中的确是一旦找到目标（满足要求）就停止继续搜索下去的。前面的错解恰恰是掉在了这样的惯性思维所造成的陷阱中。

反过来说，完全通用的解题策略是不存在的。每一个实际问题都有它的一些独特的地方需要仔细分析case-by-case地处理。