прикреплённый файл:2013-01-25.lab.py к странице LecturesVMSH/Python/2013-01-25

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Лабиринт задан массивом M×N нулей и единиц. 0 считается проходимым местом, а 1 — непроходимым. Написать программу, которая:
   5     умеет выводить лабиринт в красивом виде
   6     Проверяет, можно ли добраться из клетки (0,0) в клетку (M-1,N-1)
   7     вычисляет длину минимального пути
   8     выводит маршрут
   9 
  10     Формат ввода -- построчно 0 и 1 через пробел
  11 '''
  12 
  13 import sys
  14 
  15 def Print(Field):
  16     print "+"+"-"*len(Field[0])+"+"
  17     print "\n".join(("|"+"".join((" #."[(c==1 and 1) or (c==-1 and 2)] for c in l))+"|" for l in Field))
  18     print "+"+"-"*len(Field[0])+"+"
  19 
  20 def Flood(Field):
  21     W,H=len(Field[0]),len(Field)
  22     N=2
  23     Plan,Field[0][0]=[(0,0)],N
  24     D=((-1,0),(0,-1),(1,0),(0,1))
  25     while Plan:
  26         N+=1
  27         Oldplan,Plan=Plan,[]
  28         for x,y in Oldplan:
  29             for dx,dy in D:
  30                 if 0<=x+dx<W and 0<=y+dy<H and Field[y+dy][x+dx] == 0:
  31                     Plan.append((x+dx, y+dy))
  32                     Field[y+dy][x+dx]=N
  33 
  34 def Path(Field):
  35     D=((-1,0),(0,-1),(1,0),(0,1))
  36     W,H=len(Field[0]),len(Field)
  37     x,y=W-1,H-1
  38     N,Field[y][x]=Field[y][x],-1
  39     while x!=0 or y!=0:
  40         N-=1
  41         for dx,dy in D:
  42             if 0<=x+dx<W and 0<=y+dy<H and Field[y+dy][x+dx] == N:
  43                 x,y=x+dx,y+dy
  44                 Field[y][x]=-1
  45                 break
  46         else:
  47             print "No path"
  48             break
  49 
  50 Field=[[int(c) for c in s.split()] for s in sys.stdin]
  51 Flood(Field)
  52 Path(Field)
  53 Print(Field)