题:
下过象棋的人都知道,马只能走'日'字形(包括旋转90°的日),现在想象一下,给你一个n行m列网格棋盘,
棋盘的左下角有一匹马,请你计算至少需要几步可以将它移动到棋盘的右上角,若无法走到,则输出-1.
如n=1,m=2,则至少需要1步;若n=1,m=3,则输出-1。
解:
def f(n,m):
step = ((1,2),(2,1),(-1,-2),(-1,2),(1,-2),(-2,-1),(-2,1),(2,-1)) #每步可能行走的坐标
Isvisit = [[False]*(n+1) for _ in range(m+1)] #生成False列表(m为x坐标,n为y坐标)
Isvisit[0][0] = True #将坐标(0,0)赋值成True
visit = [(0,0)] #初始步定位到(0,0)
minCount = 0 #行走步数
while len(visit) != 0:
l = len(visit)
minCount += 1
for i in xrange(l):
a,b = visit.pop(0) #记录最后一步的坐标
for temp in step: #读取所有行走坐标,分别加到最后一步坐标上
tema = a + temp[0] #X坐标
temb = b + temp[1] #Y坐标
if tema == m and temb == n: #判断是否成功,成功即结束
return minCount
break
if tema > -1 and tema <= m and temb >-1 and temb <= n and not Isvisit[tema][temb]: #判断此步是否生成,可以生成便记录坐标,并将此坐标上False变成True
Isvisit[tema][temb] == True
visit.append((tema,temb))
print visit
else:
return -1
print f(n,m)
阅读(1489) | 评论(0) | 转发(0) |