Прикреплённый файл «lab_gen.py»
Загрузка 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)
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2011-09-26 11:35:28, 1.0 KB) [[attachment:Sav_2_ sostav_all.py]]
- [получить | показать] (2011-09-26 11:35:28, 2.0 KB) [[attachment:content.py]]
- [получить | показать] (2011-09-26 11:35:28, 1.6 KB) [[attachment:content_gen.py]]
- [получить | показать] (2011-09-26 11:35:28, 1.0 KB) [[attachment:lab.py]]
- [получить | показать] (2011-09-26 11:35:28, 4.4 KB) [[attachment:lab_gen.py]]
Вам нельзя прикреплять файлы к этой странице.