【求助】一马当先

fangweiren

下过象棋的人都知道，马只能走'日'字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘，棋盘的左下角有一匹马，请你计算至少需要几步可以将它移动到棋盘的右上角，若无法走到，则输出-1.如n=1，m=2,则至少需要1步；若n=1，m=3,则输出-1。
@Cross先生，没有一点思路，求问怎么解

crossin先生

1.把当前状态可以眺到位置记录在一个list1中，记下步数
2.然后再计算list1的所有能跳到的位置，记录在list2，记下步数，更新list1为list2
3.重复2，知道list2包含终点（成功，输出步数），或list2等于list1（失败，输出-1）

小燕smile

我这边给出一个大致的解法，你看看，希望能对你有所启发：

1. def check(x1,y1,x2,y2):     #检查是否到达指定的点
   
2.     if x1==x2 and y1==y2:
   
3.       return True
   
4.     return False
   
5. 
   
6. def find_way(x1,y1,x2,y2):
   
7.     '''由于假设是从左下角开始走，所以我只用了马的四种走法（实际有八种）,
   
8.     我假设马只能向右侧走（因为要去右上角），并且优先采用了（1,2）和（2,1）这种走法'''
   
9.     global step
   
10. 
    
11.     if check(x1+1,y1+2,x2,y2):
    
12.         step+=1
    
13.         chessboard[x1][y1]=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. 
    
20.     if check(x1+2,y1+1,x2,y2):
    
21.         step+=1
    
22.         chessboard[x1][y1]=step
    
23.         return step
    
24.     elif x1+2<x2 and y1+1<y2:
    
25.             step+=1
    
26.             chessboard[x1][y1]=step
    
27.             return find_way(x1+2,y1+1,x2,y2)
    
28. 
    
29.     if check(x1+2,y1-1,x2,y2):
    
30.         step+=1
    
31.         chessboard[x1][y1]=step
    
32.         return step
    
33.     elif x1+2<x2 and y1-1<y2:
    
34.             step+=1
    
35.             chessboard[x1][y1]=step
    
36.             return find_way(x1+2,y1-1,x2,y2)
    
37. 
    
38.     if check(x1+1,y1-2,x2,y2):
    
39.         step+=1
    
40.         chessboard[x1][y1]=step
    
41.         return step
    
42.     elif x1+1<x2 and y1-2<y2:
    
43.             step+=1
    
44.             chessboard[x1][y1]=step
    
45.             return find_way(x1+1,y1-2,x2,y2)
    
46.     return -1

复制代码

小燕smile

使用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

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先生

小燕smile 发表于 2016-4-13 16:13
这四行应该写到实际代码中，粘错了~~~
另外几点说明：
以上代码存在很多缺陷，有很大的改进空间，例如：

赞。欢迎大家多交流代码

小燕smile

晚上对上面代码中不完善的地方做了进一步修正，修正如下：

1. def check(x1,y1,x2,y2):     #检查是否到达指定的点
   
2.     if x1==x2 and y1==y2:
   
3.       return True
   
4.     return False
   
5. 
   
6. def find_way(x1,y1,x2,y2):
   
7.     '''由于假设是从左下角开始走，所以我只用了马的四种走法（实际有八种）,
   
8.     我假设马只能向右侧走（因为要去右上角），并且优先采用了（1,2）和（2,1）这种走法'''
   
9.     global step
   
10. 
    
11.     if check(x1+1,y1+2,x2,y2):
    
12.         step+=1
    
13.         chessboard[x1][y1]=step
    
14.         step+=1
    
15.         chessboard[x1+1][y1+2]=step
    
16.         return step
    
17.     elif x1+1<x2 and y1+2<y2:
    
18.             step+=1
    
19.             chessboard[x1][y1]=step
    
20.             return find_way(x1+1,y1+2,x2,y2)
    
21. 
    
22.     if check(x1+2,y1+1,x2,y2):
    
23.         step+=1
    
24.         chessboard[x1][y1]=step
    
25.         step+=1
    
26.         chessboard[x1+2][y1+1]=step
    
27.         return step
    
28.     elif x1+2<x2 and y1+1<y2:
    
29.             step+=1
    
30.             chessboard[x1][y1]=step
    
31.             return find_way(x1+2,y1+1,x2,y2)
    
32. 
    
33.     if check(x1+2,y1-1,x2,y2):
    
34.         step+=1
    
35.         chessboard[x1][y1]=step
    
36.         step+=1
    
37.         chessboard[x1+2][y1-1]=step
    
38.         return step
    
39.     elif x1+2<x2 and y1-1<y2:
    
40.             step+=1
    
41.             chessboard[x1][y1]=step
    
42.             return find_way(x1+2,y1-1,x2,y2)
    
43. 
    
44.     if check(x1+1,y1-2,x2,y2):
    
45.         step+=1
    
46.         chessboard[x1][y1]=step
    
47.         step+=1
    
48.         chessboard[x1+1][y1-2]=step
    
49.         return step
    
50.     elif x1+1<x2 and y1-2<y2:
    
51.             step+=1
    
52.             chessboard[x1][y1]=step
    
53.             return find_way(x1+1,y1-2,x2,y2)
    
54. 
    
55. #另外四种走法：
    
56. 
    
57. 
    
58. 
    
59. 
    
60. 
    
61.     if check(x1-2, y1+1, x2, y2):
    
62.         step += 1
    
63.         chessboard[x1][y1] = step
    
64.         return step
    
65.     elif 0 < x1-2 < x2 and y1+1 < y2:
    
66.             step += 1
    
67.             chessboard[x1][y1] = step
    
68.             return find_way(x1-2, y1+1, x2, y2)
    
69. 
    
70.     if check(x1-1, y1+2, x2, y2):
    
71.         step += 1
    
72.         chessboard[x1][y1] = step
    
73.         return step
    
74.     elif 0 < x1-1 < x2 and y1+2 < y2:
    
75.             step += 1
    
76.             chessboard[x1][y1] = step
    
77.             return find_way(x1-1, y1+2, x2, y2)
    
78. 
    
79.     if check(x1-1,y1-2,x2,y2):
    
80.         step+=1
    
81.         chessboard[x1][y1]=step
    
82.         return step
    
83.     elif 0 < x1-1 < x2 and 0< y1-2 < y2:
    
84.             step+=1
    
85.             chessboard[x1][y1]=step
    
86.             return find_way(x1-1,y1-2,x2,y2)
    
87. 
    
88.     if check(x1-2, y1-1, x2, y2):
    
89.         step += 1
    
90.         chessboard[x1][y1]=step
    
91.         return step
    
92.     elif 0 < x1-2 < x2 and 0 < y1-1 < y2:
    
93.             step += 1
    
94.             chessboard[x1][y1] = step
    
95.             return find_way(x1-2, y1-1, x2, y2)
    
96. 
    
97.     return -1
    
98. 
    
99. cols=9
    
100. rows=9
     
101. chessboard = [[0 for col in range(cols)]for row in range(rows) ]
     
102. step=0
     
103. print(find_way(0,0,8,8)-1)
     
104. chessboard.reverse()
     
105. for i in range(cols):
     
106.             for j in range(rows):
     
107.                 print (chessboard[i][j],'',end='',)
     
108.             print('\t')

复制代码

修正后的代码比之前稍微好些了，只是有时会存在递归太深的问题，暂时没想到具体原因

小燕smile

修正后的实际效果如下：
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)点移到左下角，并且调整了之前代码在棋盘上不会显示最后一步的问题，并且在代码中添加了另外四种走法（发现添加后在某些情况下会出现递归过深的问题，暂时未解决）