прикреплённый файл:lab_gen.py к странице LecturesVMSH/2010-12-08

   1 #!/usr/bin
   2 # coding: UTF8
   3 '''
   4 Лабиринт задан целочисленной матрицей NxN, 0 означает проходимое место, 1 — стену.
   5 
   6 Генератор входных данных
   7 '''
   8 
   9 import sys,pprint
  10 from random import randint,choice,shuffle,randrange,random
  11 
  12 DENSITY=0.3
  13 
  14 def gen(n, gen_fun, st=(0,0), en=(-1,-1)):
  15     global w,h
  16     T=[[0]*n for i in xrange(n)]
  17     w,h=len(T[0]),len(T)
  18     en=(en[0]<0 and n-1 or en[0], en[1]<0 and n-1 or en[1])
  19     T=gen_fun(T,st,en)
  20     T[st[0]][st[1]]=T[en[0]][en[1]]=0
  21     return T
  22 
  23 def gen_raw(T, st, en):
  24     '''Простейший вариант — поставим несколько случайных стен'''
  25     for i in xrange(int(w*h*DENSITY)):
  26         x,y=randint(0,w-1),randint(0,h-1)
  27         if (x,y) not in ((0,0),(w,h)):
  28             T[y][x]=1
  29     return T
  30 
  31 def gen_patt(T, st, en):
  32     '''Заполним поле шаблонами 3x3 с комнатой посередине, колоннами по углам
  33     и случайными стенками с четырёх сторон'''
  34     Walls=(1,)*int(100*DENSITY)+(0,)*int(100*(1.-DENSITY))
  35     Patts=[(r,d) for r in Walls for d in Walls]
  36     for x in xrange(0,w-1,2):
  37         for y in xrange(0,h-1,2):
  38             T[y][x],T[y+1][x+1],T[y][x+1],T[y+1][x]=(0,1)+choice(Patts)
  39     T[0][1]=T[1][0]=T[-1][-2]=T[-2][-1]=0
  40     return T
  41 
  42 def gen_patt2(T, st, en):
  43     '''Поставим колонны и случайные стенки'''
  44     for x in xrange(0,w,2):
  45         for y in xrange(0,h,2):
  46             T[y][x]=1
  47     for x in xrange(0,w):
  48         for y in xrange((x+1)%2,h,2):
  49             T[y][x]=random()<=DENSITY and 1 or 0
  50     T[0][1]=T[1][0]=T[-1][-2]=T[-2][-1]=0
  51     return T
  52 
  53 def gen_path(T, st, en):
  54     '''Протопчем все возможные пути (с учётом колонн и комнат)'''
  55     T=[[1]*w for i in xrange(h)]
  56     def path(x,y):
  57         D=[(0,2),(2,0),(0,-2),(-2,0),]; shuffle(D)
  58         T[y][x]=0   # комната
  59         for dx,dy in D:
  60             X,Y=x+dx,y+dy
  61             if X>=0 and X<w and Y>=0 and Y<h and T[Y][X]:
  62                 T[(Y+y)/2][(X+x)/2]=0 # стенка между комнатами
  63                 path(X,Y)
  64     path(*st)
  65     return T
  66 
  67 def gen_path2(T, st, en):
  68     '''Протопчем все возможные пути.
  69     В некоторый момент начнём топтать с конца'''
  70     T=[[1]*w for i in xrange(h)]
  71     D=[(0,-2),(2,0),(0,2),(-2,0)]               # направление к соседним комнатам
  72     V=[(st,range(4))]                           # комнаты которые мы хотим посетить
  73     Closed,Step=randrange(int(w*h/DENSITY/4)),0 # На каком шаге прерваться
  74     while V:
  75         if not V[-1][1]:                        # больше идти некуда
  76             V.pop()
  77             continue
  78         x,y=V[-1][0]
  79         Step+=1
  80         if Step==Closed:
  81             V.append((en,range(4)))
  82             continue
  83         dx,dy = D[V[-1][1].pop(randrange(len(V[-1][1])))]
  84         T[y][x],X,Y=0,x+dx,y+dy
  85         if X>=0 and Y>=0 and X<w and Y<h and T[Y][X]:
  86                 V.append(((X,Y),range(4)))
  87                 T[(y+Y)/2][(x+X)/2]=0           # Стенка между комнатами
  88     return T
  89 
  90 def gen_pathM(T, st, en):
  91     '''Протопчем все возможные пути одновременно с начала и с конца.
  92     Получится непроходимый лабиринт'''
  93     T=[[1]*w for i in xrange(h)]
  94     D=[(0,-2),(2,0),(0,2),(-2,0)]               # направление к соседним комнатам
  95     V=[(en,range(4)),(st,range(4))]             # комнаты которые мы хотим посетить
  96     while V:
  97         s=-randrange(2)                         # с начала или с конца
  98         if not V[s][1]:                         # больше идти некуда
  99             V.pop(s)
 100             continue
 101         x,y=V[s][0]
 102         dx,dy = D[V[s][1].pop(randrange(len(V[s][1])))]
 103         T[y][x],X,Y=0,x+dx,y+dy
 104         if X>=0 and Y>=0 and X<w and Y<h and T[Y][X]:
 105                 if s: 
 106                     V.append(((X,Y),range(4)))
 107                 else: 
 108                     V.insert(0,((X,Y),range(4)))
 109                 T[(y+Y)/2][(x+X)/2]=0           # Стенка между комнатами
 110     return T
 111 
 112 N=int(sys.argv[1])
 113 if len(sys.argv)>2:
 114     DENSITY=float(sys.argv[2])
 115 print gen(N,gen_pathM)