2025年3月16日 星期日 甲辰(龙)年 月十五 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q27: 禁止右转

时间:12-28来源:作者:点击数:42

1. 问题描述

本题来自《程序员的算法趣题》中的第27题。

在某些国家(如日本、英国)车辆是靠左通行的,开车左转比右转要舒服些。那么现在来想一下,在网格状的道路网络中,如何只靠直行或者左转到达目的地。

问题:在规整的矩形网格状道路网络中(如图1),从左下角出发到右上角,对于任意的正整数组合(m,n),总共有多少种可能的路线?条件是只能直行或左转(禁止右转),且已经通过的道路不能重复,但是允许道路有交叉。并且假定只能指定的矩形范围以内行驶。

图 1 圈定范围内的矩形网格状道路网络

图中加上了直角坐标系,并将左下角标记为(0,0),右上角标记为(m, n),并无必然性。仅为解题对照方便,且并不是一般性。

2. 分析

先从一些简单的情况开始分析以获得一些直观认识。针对简单情况得到的分析结果也为程序调试提供了简单的testcase。

显然,从出发点开始,第一次动作只能是向右走(注意,不可以右转,但是可以右行)。而且出发点

{m=1,n=1}: 显然只有一条路线。{右、上}

{m=2,n=2}: 有两条路线。{右、上、上、左、下、右、右、上};{右、右、上、上}

{m=3,n=2}: 有四条路线

图 2 几种简单情况

注意,题目并不要求最短路径,所以允许绕弯兜圈,只要不重复通过同一条边即可。

这个问题可以用深度优先搜索(DFS)方法来解决。题目并不是要求找出一条特定的合法路径,而是要找出所有可能的路径数,所以不管有没有找到合法路径,都要进行回溯继续找下一条,直到穷尽完所有的可能性。

要点:

  1. 在深度优先搜索中,需要记忆已经访问过的边以防止重复访问
  2. 由于禁止右转,所以在每一个节点处选择可能的行进方向时,需要知道上一次的行进方向
  3. 在中间的节点处,若不考虑不能的重复的限制的话有两种可行的前进方向(直进或左转),但是处于边界的节点处,选择就会受到限制

与广度优先搜索使用队列进行实现不同,深度优先搜索需要基于栈来实现。可以基于显示的栈来实现,也可以基于递归调用来隐式地实现栈处理。采用递归调用的实现方法,代码会显得非常紧凑,其代价则是执行效率的下降。

3. 实现

3.1 基本思路

图 3 递归实现基本思路

3.2 实现代码

  • import sys
  • import time
  • import random
  • from typing import List
  • # from queue import Queue
  • class Solution:
  • def NoRightTurn(self, m:int, n:int)->int:
  • """
  • :m: number of column (horizontal width) of the rectangular grid network
  • :n: number of row (vertical height) of the rectangular grid network
  • :
  • :ret: the number of the total valid path
  • """
  • # Initialization
  • start = (1,0)
  • target = (m,n)
  • visited = [{(0,0),(1,0)}]
  • preMove = 3
  • def core(start, prevMove, visited)->int:
  • """
  • :target: A tuple (x,y) to represent the coordinate of start point
  • :prevMove: The previous move. 0: up; 1: left; 2:down; 3: right
  • :visited: A list to hold already-visited edges to avoid repeated visit
  • : Each edge is represented by a set of tuple:{(x0,y0),(x1,y1)}.
  • :ret: The number of the total valid path
  • """
  • # print('core: ', start, prevMove, visited)
  • if start == target:
  • # print('\tcore({0}, {1}, {2} = 1'.format(start,prevMove,visited))
  • return 1 # Found one valid path
  • num = 0
  • for k in range(2):
  • newMove = (prevMove + k)%4
  • x = start[0]
  • if newMove == 1:
  • x = x - 1
  • elif newMove == 3:
  • x = x + 1
  • y = start[1]
  • if newMove == 0:
  • y = y + 1
  • elif newMove == 2:
  • y = y - 1
  • # print('\tk={0}, x={1}, y={2}'.format(k,x,y))
  • if (x >= 0 and x <= m) and (y >= 0 and y <= n):
  • newStart = (x,y)
  • edge = set([start,newStart])
  • # print(edge)
  • if edge not in visited:
  • newVisited = visited + [edge]
  • num = num + core(newStart, newMove, newVisited)
  • # print('\tcore({0}, {1}, {2} = {3}'.format(start,prevMove,visited,num))
  • return num
  • return core(start,preMove,visited)

3.3测试例及运行结果

  • if __name__ == '__main__':
  • sln = Solution()
  • # m,n = 1,1
  • # print('m = {0}, n = {1}, numPath = {2}'.format(m,n,sln.NoRightTurn(m,n)))
  • # m,n = 1,2
  • # print('m = {0}, n = {1}, numPath = {2}'.format(m,n,sln.NoRightTurn(m,n)))
  • # m,n = 2,1
  • # print('m = {0}, n = {1}, numPath = {2}'.format(m,n,sln.NoRightTurn(m,n)))
  • m,n = 2,2
  • tStart = time.time()
  • num = sln.NoRightTurn(m,n)
  • tCost = time.time() - tStart
  • print('m = {0}, n = {1}, numPath = {2}, tCost = {3}(sec)'.format(m,n,num,tCost))
  • m,n = 3,2
  • tStart = time.time()
  • num = sln.NoRightTurn(m,n)
  • tCost = time.time() - tStart
  • print('m = {0}, n = {1}, numPath = {2}, tCost = {3}(sec)'.format(m,n,num,tCost))
  • m,n = 4,4
  • tStart = time.time()
  • num = sln.NoRightTurn(m,n)
  • tCost = time.time() - tStart
  • print('m = {0}, n = {1}, numPath = {2}, tCost = {3}(sec)'.format(m,n,num,tCost))
  • m,n = 5,4
  • tStart = time.time()
  • num = sln.NoRightTurn(m,n)
  • tCost = time.time() - tStart
  • print('m = {0}, n = {1}, numPath = {2}, tCost = {3}(sec)'.format(m,n,num,tCost))
  • m,n = 6,4
  • tStart = time.time()
  • num = sln.NoRightTurn(m,n)
  • tCost = time.time() - tStart
  • print('m = {0}, n = {1}, numPath = {2}, tCost = {3}(sec)'.format(m,n,num,tCost))
  • m,n = 6,6
  • tStart = time.time()
  • num = sln.NoRightTurn(m,n)
  • tCost = time.time() - tStart
  • print('m = {0}, n = {1}, numPath = {2}, tCost = {3}(sec)'.format(m,n,num,tCost))

运行结果如下:

  • m = 2, n = 2, numPath = 2, tCost = 0.0(sec)
  • m = 3, n = 2, numPath = 4, tCost = 0.0009949207305908203(sec)
  • m = 4, n = 4, numPath = 141, tCost = 0.00797891616821289(sec)
  • m = 5, n = 4, numPath = 601, tCost = 0.04787850379943848(sec)
  • m = 6, n = 4, numPath = 2760, tCost = 0.26329922676086426(sec)
  • m = 6, n = 6, numPath = 312533, tCost = 59.706143617630005(sec)

Can we do better?

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门