程序员的算法趣题Q08: 优秀的扫地机器人

1.问题描述

现在市面上有些扫地机器人有时候会反复地清扫某一个地方。

假设有一款比较只能的知道避免重复清扫一个地方的扫地机器人，限定它只能前后左右移动，每次移动一格。举个例子，如果第1次向后移动，那么连续移动三次后，它的轨迹会出现9种情况，如下所示(0表示起点的位置，k={1,2,3}表示经过k步移动后机器人所在的位置)。

求这个机器移动12次时，有多少种移动路径？

2.解题分析

深度优先路径遍历搜索（我杜撰的？要查一查^-^）问题。

3.代码及测试

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 28 08:30:34 2021

@author: chenxy
"""

import sys
import time
import datetime
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque

class Solution:
    def mopRobot(self, N: int) -> int:
        """
        :N:   The total number of steps
        :ret: The total number of moving paths
        """                
        
        def explore(pathHistory, numSteps):
            # Baseline case: numSteps = 0 means the move is finished.
            if numSteps == 0:
                return 1
            
            # Explore the four directions to search the allowed move
            sum    = 0
            # up move
            curPos    = pathHistory[-1]
            nxtPos    = tuple([curPos[0], curPos[1] + 1])
            if nxtPos not in pathHistory:
                sum += explore(pathHistory + [nxtPos], numSteps-1)
                
            # down move
            curPos    = pathHistory[-1]
            nxtPos    = tuple([curPos[0], curPos[1] - 1])
            if nxtPos not in pathHistory:
                sum += explore(pathHistory + [nxtPos], numSteps-1)                
                
            # left move
            curPos    = pathHistory[-1]
            nxtPos    = tuple([curPos[0] - 1, curPos[1]])
            if nxtPos not in pathHistory:
                sum += explore(pathHistory + [nxtPos], numSteps-1)                                

            # right move
            curPos    = pathHistory[-1]
            nxtPos    = tuple([curPos[0] + 1, curPos[1]])
            if nxtPos not in pathHistory:
                sum += explore(pathHistory + [nxtPos], numSteps-1)                                                
                
            return sum

        return explore([(0,0)],N)        

if __name__ == '__main__':        
            
    sln    = Solution()    

    for N in range(1,13):
        tStart = time.time()
        ans    = sln.mopRobot(N)
        tCost  = time.time() - tStart
        print('N={0}, ans={1}, tCost = {2:.3f}(sec)'.format(N,ans,tCost))  

3.1 运行结果：

N=2, ans=12, tCost = 0.000(sec)

N=4, ans=100, tCost = 0.000(sec)

N=6, ans=780, tCost = 0.001(sec)

N=8, ans=5916, tCost = 0.006(sec)

N=10, ans=44100, tCost = 0.057(sec)

N=12, ans=324932, tCost = 0.454(sec)

N=14, ans=2374444, tCost = 3.502(sec)

4.优化

Python种list的查询相比dict查询要低效得多，如果用dict来存储路径历史pathHistory的话应该可以快很多。但是用dict表示的话，路径的最后位置（即当前位置）就需要另行记忆。