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

《程序员的算法趣题》Q08 优秀的扫地机器

第一次写博客,请多见谅。

目前在看图灵程序设计丛书绝云译的《程序员的算法趣题》,书中是用Ruby实现的。因为没学过Ruby,只能大致理解。python也是刚入门,感觉网上的答案有点难理解,自己尝试写了一个比较初级的代码。

问题描述

现在有很多制造商都在卖扫地机器人,可是这些机器人有时候会反复清扫某一个地方。假设有一款机器人不会反复清扫同一个地方,它只能前后左右移动。举个例子,如果第1次向后移动,那么连续移动3次时,就会有以下9种情况(见图)。又因为第1次移动可以是前后左右4种情况,所以移动3次时全部路径有 9 * 4 = 36 种。那么求这个机器人移动12次时,有多少种移动路径?(P029)
《程序员的算法趣题》Q08 优秀的扫地机器人
思路

灵感来自迷宫的回溯算法
因为移动12次,所以先建立一个25*25的全零二维数组web。
点的初始位置是web[12][12],并赋值1.
定义一个函数,对点进行上下左右移动,并判断是否是否已经过,完成一次移动,再调用自身。

《程序员的算法趣题》Q08 优秀的扫地机器人
web=list([0 for i in range(25)] for j in range(25))#建立一个25*25的全零二维数组web
count=0#计数
web[12][12]=1
def move(x,y,k):#x是点位置的横坐标,y是纵坐标,k是移动次数
global count
if k!=12:
for i in range(4):#0上 1下 2左 3右
if i == 0 and web[x][y + 1] == 0: web[x][y + 1] = 1;move(x, y + 1, k + 1);web[x][y + 1] = 0#调用自身后回溯,还原为0
if i == 1 and web[x][y - 1] == 0: web[x][y - 1] = 1;move(x, y - 1, k + 1);web[x][y - 1] = 0
if i == 2 and web[x - 1][y] == 0: web[x - 1][y] = 1;move(x - 1, y, k + 1);web[x - 1][y] = 0
if i == 3 and web[x + 1][y] == 0: web[x + 1][y] = 1;move(x + 1, y, k + 1);web[x + 1][y] = 0
else:
count=count+1#完成移动12次,此处print可看具体路径
move(12,12,0)
print(count)

结果
有324932种。
比较简单,请多指教。