如上所述,在满足相遇的两种条件之一后即提前退出会导致大量的路径(满足相遇条件后的路径分岔)被漏算了。正确的做法是只要不出界,就必须一直走到底。由此可以看出在之前的错误的解答中的以下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一直增加直到到达边界不得不转向为止。
- # -*- 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)
在很多的路径遍历搜索问题中的确是一旦找到目标(满足要求)就停止继续搜索下去的。前面的错解恰恰是掉在了这样的惯性思维所造成的陷阱中。
反过来说,完全通用的解题策略是不存在的。每一个实际问题都有它的一些独特的地方需要仔细分析case-by-case地处理。