Chinaunix首页 | 论坛 | 博客
  • 博客访问: 136607
  • 博文数量: 34
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 252
  • 用 户 组: 普通用户
  • 注册时间: 2014-05-27 20:04
文章分类

全部博文(34)

文章存档

2018年(1)

2017年(23)

2016年(10)

我的朋友

分类: 系统运维

2016-12-09 10:24:23

题:
下过象棋的人都知道,马只能走'日'字形(包括旋转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)
阅读(1426) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~