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

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?