本题来自《程序员的算法趣题》中的第27题。
在某些国家(如日本、英国)车辆是靠左通行的,开车左转比右转要舒服些。那么现在来想一下,在网格状的道路网络中,如何只靠直行或者左转到达目的地。
问题:在规整的矩形网格状道路网络中(如图1),从左下角出发到右上角,对于任意的正整数组合(m,n),总共有多少种可能的路线?条件是只能直行或左转(禁止右转),且已经通过的道路不能重复,但是允许道路有交叉。并且假定只能指定的矩形范围以内行驶。
图 1 圈定范围内的矩形网格状道路网络
图中加上了直角坐标系,并将左下角标记为(0,0),右上角标记为(m, n),并无必然性。仅为解题对照方便,且并不是一般性。
先从一些简单的情况开始分析以获得一些直观认识。针对简单情况得到的分析结果也为程序调试提供了简单的testcase。
显然,从出发点开始,第一次动作只能是向右走(注意,不可以右转,但是可以右行)。而且出发点
{m=1,n=1}: 显然只有一条路线。{右、上}
{m=2,n=2}: 有两条路线。{右、上、上、左、下、右、右、上};{右、右、上、上}
{m=3,n=2}: 有四条路线
图 2 几种简单情况
注意,题目并不要求最短路径,所以允许绕弯兜圈,只要不重复通过同一条边即可。
这个问题可以用深度优先搜索(DFS)方法来解决。题目并不是要求找出一条特定的合法路径,而是要找出所有可能的路径数,所以不管有没有找到合法路径,都要进行回溯继续找下一条,直到穷尽完所有的可能性。
要点:
与广度优先搜索使用队列进行实现不同,深度优先搜索需要基于栈来实现。可以基于显示的栈来实现,也可以基于递归调用来隐式地实现栈处理。采用递归调用的实现方法,代码会显得非常紧凑,其代价则是执行效率的下降。
图 3 递归实现基本思路
- 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)
- 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?