Crossin的编程教室

标题: 【求助】一马当先 [打印本页]

作者: fangweiren    时间: 2016-2-17 10:37
标题: 【求助】一马当先
下过象棋的人都知道,马只能走'日'字形(包括旋转90°的日),现在想象一下,给你一个n行m列网格棋盘,棋盘的左下角有一匹马,请你计算至少需要几步可以将它移动到棋盘的右上角,若无法走到,则输出-1.如n=1,m=2,则至少需要1步;若n=1,m=3,则输出-1。
@Cross先生,没有一点思路,求问怎么解

作者: crossin先生    时间: 2016-2-17 11:54
1.把当前状态可以眺到位置记录在一个list1中,记下步数
2.然后再计算list1的所有能跳到的位置,记录在list2,记下步数,更新list1为list2
3.重复2,知道list2包含终点(成功,输出步数),或list2等于list1(失败,输出-1)
作者: 小燕smile    时间: 2016-4-13 16:00
我这边给出一个大致的解法,你看看,希望能对你有所启发:
  1. def check(x1,y1,x2,y2):     #检查是否到达指定的点
  2.     if x1==x2 and y1==y2:
  3.       return True
  4.     return False

  5. def find_way(x1,y1,x2,y2):
  6.     '''由于假设是从左下角开始走,所以我只用了马的四种走法(实际有八种),
  7.     我假设马只能向右侧走(因为要去右上角),并且优先采用了(1,2)和(2,1)这种走法'''
  8.     global step

  9.     if check(x1+1,y1+2,x2,y2):
  10.         step+=1
  11.         chessboard[x1][y1]=step
  12.         return step
  13.     elif x1+1<x2 and y1+2<y2:
  14.             step+=1
  15.             chessboard[x1][y1]=step
  16.             return find_way(x1+1,y1+2,x2,y2)

  17.     if check(x1+2,y1+1,x2,y2):
  18.         step+=1
  19.         chessboard[x1][y1]=step
  20.         return step
  21.     elif x1+2<x2 and y1+1<y2:
  22.             step+=1
  23.             chessboard[x1][y1]=step
  24.             return find_way(x1+2,y1+1,x2,y2)

  25.     if check(x1+2,y1-1,x2,y2):
  26.         step+=1
  27.         chessboard[x1][y1]=step
  28.         return step
  29.     elif x1+2<x2 and y1-1<y2:
  30.             step+=1
  31.             chessboard[x1][y1]=step
  32.             return find_way(x1+2,y1-1,x2,y2)

  33.     if check(x1+1,y1-2,x2,y2):
  34.         step+=1
  35.         chessboard[x1][y1]=step
  36.         return step
  37.     elif x1+1<x2 and y1-2<y2:
  38.             step+=1
  39.             chessboard[x1][y1]=step
  40.             return find_way(x1+1,y1-2,x2,y2)
  41.     return -1
复制代码

作者: 小燕smile    时间: 2016-4-13 16:03
使用py3.4编写,基于win7平台下面的pycharm4.5测试,下面是编写的测试用例:
  1. cols=8
  2. rows=8
  3. chessboard=[[0 for col in range(cols)] for row in range(rows)]
  4. step=0
  5. print(find_way(0,0,7,7))
  6. for i in range(rows):
  7.             for j in range(cols):
  8.                 print(chessboard[i][j],'',end='',)
  9.             print('\t')
复制代码
注意:我的坐标系是从(0,0)开始的,故(7,7)在实际坐标中为(6,6)
测试结果:
-1
1 0 0 0 0 0 0 0        
0 0 2 0 0 0 0 0        
0 0 0 0 3 0 0 0        
0 0 0 0 0 0 4 0        
0 0 0 0 0 0 0 0        
0 0 0 0 0 5 0 0        
0 0 0 0 0 0 0 0        
0 0 0 0 0 0 0 0
作者: 小燕smile    时间: 2016-4-13 16:13
  1. cols=8
  2. rows=8
  3. chessboard=[[0 for col in range(cols)] for row in range(rows)]
  4. step=0
复制代码
这四行应该写到实际代码中,粘错了~~~
另外几点说明:
以上代码存在很多缺陷,有很大的改进空间,例如:
1.马在某一点最多存在八种走法,需要根据实际的位置判断马实际满足几种下一步走法,而本算法只写了四种;
2.if语句的顺序影响了下一步走法尝试的顺序,故本算法只得出了其中一种走法,没有遍历出所有的走法来;
3.其他尚未写出的缺陷
希望看到该代码的大神能够完善出一个能求的在任一点寻路到另外一点的最短路径算法,互相学习!
由于没有怎么学习过算法,全是自己瞎捉摸的,希望能够抛砖引玉!
作者: crossin先生    时间: 2016-4-13 21:15
小燕smile 发表于 2016-4-13 16:13
这四行应该写到实际代码中,粘错了~~~
另外几点说明:
以上代码存在很多缺陷,有很大的改进空间,例如:

赞。欢迎大家多交流代码
作者: 小燕smile    时间: 2016-4-13 21:30
晚上对上面代码中不完善的地方做了进一步修正,修正如下:
  1. def check(x1,y1,x2,y2):     #检查是否到达指定的点
  2.     if x1==x2 and y1==y2:
  3.       return True
  4.     return False

  5. def find_way(x1,y1,x2,y2):
  6.     '''由于假设是从左下角开始走,所以我只用了马的四种走法(实际有八种),
  7.     我假设马只能向右侧走(因为要去右上角),并且优先采用了(1,2)和(2,1)这种走法'''
  8.     global step

  9.     if check(x1+1,y1+2,x2,y2):
  10.         step+=1
  11.         chessboard[x1][y1]=step
  12.         step+=1
  13.         chessboard[x1+1][y1+2]=step
  14.         return step
  15.     elif x1+1<x2 and y1+2<y2:
  16.             step+=1
  17.             chessboard[x1][y1]=step
  18.             return find_way(x1+1,y1+2,x2,y2)

  19.     if check(x1+2,y1+1,x2,y2):
  20.         step+=1
  21.         chessboard[x1][y1]=step
  22.         step+=1
  23.         chessboard[x1+2][y1+1]=step
  24.         return step
  25.     elif x1+2<x2 and y1+1<y2:
  26.             step+=1
  27.             chessboard[x1][y1]=step
  28.             return find_way(x1+2,y1+1,x2,y2)

  29.     if check(x1+2,y1-1,x2,y2):
  30.         step+=1
  31.         chessboard[x1][y1]=step
  32.         step+=1
  33.         chessboard[x1+2][y1-1]=step
  34.         return step
  35.     elif x1+2<x2 and y1-1<y2:
  36.             step+=1
  37.             chessboard[x1][y1]=step
  38.             return find_way(x1+2,y1-1,x2,y2)

  39.     if check(x1+1,y1-2,x2,y2):
  40.         step+=1
  41.         chessboard[x1][y1]=step
  42.         step+=1
  43.         chessboard[x1+1][y1-2]=step
  44.         return step
  45.     elif x1+1<x2 and y1-2<y2:
  46.             step+=1
  47.             chessboard[x1][y1]=step
  48.             return find_way(x1+1,y1-2,x2,y2)

  49. #另外四种走法:





  50.     if check(x1-2, y1+1, x2, y2):
  51.         step += 1
  52.         chessboard[x1][y1] = step
  53.         return step
  54.     elif 0 < x1-2 < x2 and y1+1 < y2:
  55.             step += 1
  56.             chessboard[x1][y1] = step
  57.             return find_way(x1-2, y1+1, x2, y2)

  58.     if check(x1-1, y1+2, x2, y2):
  59.         step += 1
  60.         chessboard[x1][y1] = step
  61.         return step
  62.     elif 0 < x1-1 < x2 and y1+2 < y2:
  63.             step += 1
  64.             chessboard[x1][y1] = step
  65.             return find_way(x1-1, y1+2, x2, y2)

  66.     if check(x1-1,y1-2,x2,y2):
  67.         step+=1
  68.         chessboard[x1][y1]=step
  69.         return step
  70.     elif 0 < x1-1 < x2 and 0< y1-2 < y2:
  71.             step+=1
  72.             chessboard[x1][y1]=step
  73.             return find_way(x1-1,y1-2,x2,y2)

  74.     if check(x1-2, y1-1, x2, y2):
  75.         step += 1
  76.         chessboard[x1][y1]=step
  77.         return step
  78.     elif 0 < x1-2 < x2 and 0 < y1-1 < y2:
  79.             step += 1
  80.             chessboard[x1][y1] = step
  81.             return find_way(x1-2, y1-1, x2, y2)

  82.     return -1

  83. cols=9
  84. rows=9
  85. chessboard = [[0 for col in range(cols)]for row in range(rows) ]
  86. step=0
  87. print(find_way(0,0,8,8)-1)
  88. chessboard.reverse()
  89. for i in range(cols):
  90.             for j in range(rows):
  91.                 print (chessboard[i][j],'',end='',)
  92.             print('\t')
复制代码
修正后的代码比之前稍微好些了,只是有时会存在递归太深的问题,暂时没想到具体原因
作者: 小燕smile    时间: 2016-4-13 21:33
修正后的实际效果如下:
6
0 0 0 0 0 0 0 0 7        
0 0 0 0 0 0 6 0 0        
0 0 0 0 0 0 0 0 0        
0 0 0 0 0 0 0 5 0        
0 0 0 0 0 0 0 0 0        
0 0 0 0 0 0 4 0 0        
0 0 0 0 3 0 0 0 0        
0 0 2 0 0 0 0 0 0        
1 0 0 0 0 0 0 0 0
修正后,将(0,0)点移到左下角,并且调整了之前代码在棋盘上不会显示最后一步的问题,并且在代码中添加了另外四种走法(发现添加后在某些情况下会出现递归过深的问题,暂时未解决)




欢迎光临 Crossin的编程教室 (https://bbs.crossincode.com/) Powered by Discuz! X2.5