马踏棋盘

RIXO

呃，刚看了个走迷宫的python，发现好像能用在马踏棋盘上面，结果，我就来提问了！！！
问题，为什么这个文件跑贼慢！！！
怎么改能快点，我看人家跑迷宫挺快的啊

1. def solution(path,dep):
   
2.     if dep == n**2:
   
3.         paths.append(path)
   
4.         return path
   
5. 
   
6.     for each_mv in move:
   
7.         node = [path[-1][0]+each_mv[0],path[-1][1]+each_mv[1]]
   
8.         if -1 not in node and -2 not in node and n+1 not in node and n not in node and node not in path :
   
9.             path.append(node)
   
10.             dep +=1
    
11.             board[node[0]][node[1]] = dep
    
12.             solution(path,dep)
    
13.             path.pop(-1)
    
14.             dep -= 1
    
15.         
    
16. 
    
17. def main():
    
18.     solution(path,dep)
    
19.     for each in paths:
    
20.         print(each)
    
21.    
    
22. 
    
23. if __name__ == '__main__':
    
24.     move = [[x,y] for x in [-2,-1,1,2] for y in [-2,-1,1,2] if abs(x) != abs(y)]
    
25.     n = 8
    
26.     board = [[0 for i in range(n)] for i in range(n)]
    
27.     path = [[2,3]]
    
28.     paths = []
    
29.     dep = 0
    
30.     main()
    
31. 
    

复制代码

claws0n

马踏棋盘如果用回溯法好像是 O(n!)。没有用分支法的话，好像就这么慢了~

RIXO

claws0n 发表于 2018-9-23 22:09
马踏棋盘如果用回溯法好像是 O(n!)。没有用分支法的话，好像就这么慢了~

呃，咋改，还有回溯法这些在小甲鱼数据结构视频里面有木有

claws0n

RIXO 发表于 2018-9-23 22:11
呃，咋改，还有回溯法这些在小甲鱼数据结构视频里面有木有

还不会，没研究到那里。
有讲 61集，但我觉得还有进步的空间

塔利班

算法，数据结构从来没看过，有机会看看，有视频吗
是不是以C的为主？

RIXO

claws0n 发表于 2018-9-23 22:17
还不会，没研究到那里。
有讲 61集，但我觉得还有进步的空间

我突然好恨那个发马踏棋盘python实现的人，这题，我第一眼看的时候，感觉，简单！
然后开始写代码，卡了3个小时。。。写出来了，不知道跑的结果对不对，因为根本跑不出来
然后，准备看别人代码，都是C和C++的，看的一知半解
难受的想砸键盘！！！

claws0n

塔利班 发表于 2018-9-23 22:21
算法，数据结构从来没看过，有机会看看，有视频吗
是不是以C的为主？

嗯，C
论坛可以找到，链去 B 站的
小甲鱼的有一点点散

塔利班

claws0n 发表于 2018-9-23 22:25
嗯，C
论坛可以找到，链去 B 站的
小甲鱼的有一点点散

。。我C语言是真0基础，= =

claws0n

塔利班 发表于 2018-9-23 22:29
。。我C语言是真0基础，= =

哥哥是学面对对象的，回来看面对过程的 C，我怕哥哥看不下去
哥哥已经很厉害啦~

塔利班

claws0n 发表于 2018-9-23 22:38
哥哥是学面对对象的，回来看面对过程的 C，我怕哥哥看不下去
哥哥已经很厉害啦~

没有，我之前什么软件基础都没，就跟着小甲鱼学的，，专业学电的，按理说也该学点C,但是基本大学都跑路玩游戏啦

幽梦三影

放弃算法吧，很痛苦（我是没爱了）