本帖最后由 久疤K 于 2018-7-5 14:07 编辑
字典太大了,费时间,这个解法非常快
- import time
- def ti(func):
- def call(*v):
- s = time.time()
- r = func(*v)
- t = time.time()
- print(func.__name__,t-s)
- return r
- return call
- def _go(lss,now,end,res,ress):
- i,j = now
- if lss[i][j]==0 or now in res:
- return
- res.append(now)
- if now==end:
- ress.append(res)
- return
- tmp = []
- if i > 0:
- _go(lss,(i-1,j),end,res.copy(),ress)
- if i < len(lss)-1:
- _go(lss,(i+1,j),end,res.copy(),ress)
- if j > 0:
- _go(lss,(i,j-1),end,res.copy(),ress)
- if j < len(lss[i])-1:
- _go(lss,(i,j+1),end,res.copy(),ress)
- def go(lss,start,end):
- ress = []
- _go(lss,start,end,[],ress)
- return ress
- @ti
- def fun():
- room = [[1 ,0, 1, 0, 0, 1 ,0, 1, 0, 0, 0],
- [1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1],
- [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
- [1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1],
- [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
- [0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0],
- [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
- [1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1],
- [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
- [1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
- [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
- [0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0],
- [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1],
- [1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1],
- [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
- [1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1],
- [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1],
- [0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0],
- [0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1]]
- start = (0,0)
- end = (len(room)-1,len(room[-1])-1)
- ress = go(room,start,end)
- return ress
- def main():
- ress = fun()
- print("total: " ,len(ress))
- print('None' if len(ress)==0 else ress[0])
- if __name__ == "__main__":
- main()
复制代码- res:
- fun 0.002000093460083008
- total: 1
- [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 6), (6, 6), (7, 6), (7, 7), (8, 7), (9, 7), (10, 7), (10, 8), (11, 8), (12, 8), (13, 8), (13, 7), (14, 7), (15, 7), (16, 7), (16, 8), (17, 8), (18, 8), (18, 9), (18, 10)]
复制代码 |