Прикреплённый файл «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 из ссылки «[получить]», так как он чисто внутренний и может измениться.

Вам нельзя прикреплять файлы к этой странице.