程序员的算法趣题Q34: 会有几次命中注定的相遇
目录
1. 问题描述
假设存在如下图的正方形,该正方形被划分成了边长为1的正方形的格。男生从A到B,女生从B到A,分别沿着最短路径以相同速度前行(两人同步,每次都横向或纵向各走一格)。如果符合以下情形,则判定为“命中注定的相遇”
- 两次同时停在同一直线内的定点上(相互可见状态)
- 在同一顶点交汇(相互接触状态)
边长为3时,几种成功和失败的例子如上图所示。
问题:边长为6时,发生“命中注定的相遇”的情况共有多少种?
2. 解题分析
两人都是以最短距离行进,因此男生只有{向右,向下}两种选项,女生只有{向左,向上}两种选项,两人的组合动作因此就是四种:
(1) {男:右;女:左};
(2) {男:下;女:左};
(3) {男:右;女:上};
(4) {男:下;女:上};
每前进一步,进行是否符合条件的判断,如果是符合条件(2)--相互解除状态 ,则直接判断成功;如果是符合条件(1)--相互可见状态,将相互可见次数加1,如果相互可见次数到达2则判定成功;如果女生已经跑到男生的左上位置而还尚未满足条件的话,则可以判定失败;最后(作为边界条件),如果发生越界的话也判定失败。
这种类型的问题很适合于用递归的方式实现(唯一需要担心的是递归深度),算法流程如下所示:
3. 代码及测试
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 19 08:24:18 2021
@author: chenxy
"""
import sys
import time
import datetime
import math
import random
from typing import List
# from queue import Queue
from collections import deque
import itertools as it
from math import sqrt, floor, ceil
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 == womanX and manY == womanY:
total_count += 1
# print(total_count)
return
if manX == womanX or manY == womanY:
meet += 1
if meet == 2:
total_count += 1
# print(total_count)
return
# 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 -- No need, Should not come to this point.
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 = 15752, tCost = 0.026(sec)
4. 后记
这道题目算是最近几道问题感觉最为轻松的,难得地很快就想清楚了解决方案。
然而,令人尴尬的是,答案错了。更令人尴尬的是,“偷看”了原书答案以及CSDN上其他小伙伴们贴出来的答案,基本思路是一致的,运行别人的代码也的确给出了正确答案,可是反复对比看仍然没有看出自己的代码究竟错在哪儿了—自信心受到了一万点暴击。
但是,与“看到一个正确的答案后:喔,原来如此”相比,也许看一个错误的答案并揪出其中的八阿哥(BUG)更具有挑战性,也更有助益。所以,这里还是厚着脸皮贴出来供大家批判,并期待有人帮助我指出哪儿错了^-^.
【2021-09-21】想明白了,问题出在以上流程中的提前退出。题目要求的是所有路径中满足题设条件的路径数,必须遍历所有的路径并搜索到底才能得到正确的结果。举个例说,在前面图示的成功示例2中,A和B相遇于(2,1)点,此后他们还将沿不同的路径(及他们的组合)到达各自的终点,如果在相遇于(2,1)点处就提前退出的话,这些路径就合计为一条路径了,因此导致得到的路径数远远小于正解答案。本题的订正题解分析和代码参见: Q34: 会有几次命中注定的相遇(2)https://blog.csdn.net/chenxy_bwave/article/details/120415123https://blog.csdn.net/chenxy_bwave/article/details/120415123
上一篇:Q33: 飞车与角行的棋步
下一篇:Q35: 0和7的回文数
本系列总目录参见:程序员的算法趣题:详细分析和Python全解
相关文章
- 算法与数据结构对程序员的重要性
- 程序员的算法趣题Q63: 迷宫会合
- 程序员的算法趣题Q61: 不交叉一笔画下去
- 程序员的算法趣题Q67: 不挨着坐是一种礼节吗?
- 程序员的算法趣题Q50: 完美洗牌
- 程序员的算法趣题Q44: 质数矩阵
- 程序员的算法趣题Q22: 不缠绕的纸杯电话
- 程序员的算法趣题Q18: 水果酥饼日
- 程序员的算法趣题Q14: 国名接龙
- 程序员的算法趣题Q13: 满足字母算式的解法
- 程序员的算法趣题Q11: 斐波那契数列
- 程序员的算法趣题Q10: 轮盘的最大值
- 程序员的算法趣题Q08: 优秀的扫地机器人
- 程序员的算法趣题Q53: 同数包夹
- 程序员的算法趣题Q28: 社团活动的最优分配方案
- 程序员的算法趣题Q03: 翻牌
- 程序员的算法趣题Q15: 走楼梯
- 程序员的算法趣题Q21--异或杨辉三角形
- 程序员的算法趣题Q27: 禁止右转
- 程序员的算法趣题Q42: 将牌洗为逆序
- 程序员的算法趣题Q16:3根绳子折成四边形
- 程序员的算法趣题Q04:切分木棒