Прикреплённый файл «labdijkstra.py»
Загрузка 1 #!/usr/bin/env python
2 # coding: utf
3 '''
4 Лабиринт задаётся списком списков (двумерным массивом) M x N, в котором ненулевой элемент обозначает стену, а нулевой — свободное место. Переходить с одного свободного места на другое можно только на одну клетку по горизонтали или вертикали.
5
6 Выяснить, можно ли добраться из клетки [0][0] в клетку [N-1][M-1],
7 попутно вычислив длину минимального пути
8 '''
9
10 def out(T,frame=""):
11 if frame: print frame*(len(T[0])+2)
12 for l in T:
13 print frame+"".join([c==0 and " " or c==1 and "#" or str(c-1)[-1] for c in l])+frame
14 if frame: print frame*(len(T[0])+2)
15
16 T=input() # Лабиринт вводится по правилам Python
17 out(T,"+")
18 M,N=len(T[0]),len(T)
19
20 Move=((-1,0),(0,1),(1,0),(0,-1))
21 i,Front=1,[(0,0)]
22 while Front:
23 i+=1
24 NewFront=[]
25 for y,x in Front:
26 T[y][x]=i
27 for dx, dy in Move:
28 if 0<=y+dy<N and 0<=x+dx<M and T[y+dy][x+dx]==0:
29 NewFront.append((y+dy,x+dx))
30 if T[N-1][M-1]!=0:
31 out(T,"+")
32 print T[N-1][M-1]-1
33 break
34 Front=NewFront
35 else:
36 print "NO"
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2011-12-14 16:25:52, 1.0 KB) [[attachment:Avyshlovlab.py]]
- [получить | показать] (2011-12-14 13:37:48, 2.2 KB) [[attachment:floyd-warshell.py]]
- [получить | показать] (2011-12-14 13:39:03, 1.3 KB) [[attachment:labdijkstra.py]]
- [получить | показать] (2011-12-14 13:39:59, 0.8 KB) [[attachment:labpur.py]]
- [получить | показать] (2011-12-13 22:42:54, 2.2 KB) [[attachment:ray_lab.py]]
Вам нельзя прикреплять файлы к этой странице.