[Mummy Maze] 宽度优先搜索
生活随笔
收集整理的這篇文章主要介紹了
[Mummy Maze] 宽度优先搜索
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
有個小游戲ms很有意思 叫Mummy Maze
這邊有一個下載地址 有興趣的可以試試
http://www.jz5u.com/Soft/games/chess/20301.html
我也在玩 不過我寫了一個搜索程序
算法很裸 但是程序很長
一個沒有任何優化剪枝的BFS
事實上由于地圖很小 根本不需要什么優化就可以秒閃
?
寫程序之前先要對這個游戲的內容進行觀察
我的程序是游戲的簡化版 只能對付木乃伊（紅 白）
蝎子 鐵門之類沒有考慮到 以后會+上吧
白紅木乃伊的差別在于優先走行還是走列
如果你在木乃伊左上方 白木乃伊會先向上 而紅木乃伊則會先向左
前提是沒有阻礙 有阻礙的話會根據阻礙和優先級確定怎么走
確定了木乃伊行動的規律
模擬就可以了
?
另外還需要考慮讀入
我把讀入分為三塊
地圖信息 墻信息 和 木乃伊信息
地圖由一個矩陣組成 X=邊界或陷阱 O=空地 M/U/Y=木乃伊 T=探險家 D=出口
墻用邊集數組給出 用0到n^2-1給每個方格標號 把格子抽象為點 兩個格子之間有墻就確定一條邊
木乃伊信息分別給出每個木乃伊的顏色 紅為R 白為L
給出一個樣例吧
就是上圖
?
Sample.in
6 6
XXXXXXXX
XOOOOOOX
XOOOOOOX
XOOOOOOX
XOOOOOOX
XOOTOOOX
XOOOMOOX
XXXXXXDX
14
6 7
12 13
12 18
18 19
19 20
13 14
9 15
11 17
17 16
21 22
21 27
27 28
27 33
26 32
Mummy M:L
Sample.out
UUUULLRDRDRRDDDRD
?
?
Mummy.pas 1 const2 maxm=3;
3 maxq=100000;
4 maxa=500;
5 maxn=10;
6 maxh=1000000;
7 bigprime=299983;
8 dx:array[1..5] of longint=(1,0,-1,0,0);
9 dy:array[1..5] of longint=(0,1,0,-1,0);
10 type
11 hnode=
12 record
13 addr:longint;
14 next:longint;
15 end;
16 qnode=
17 record
18 mx,my:array[1..maxm]of longint;
19 mk:array[1..maxm]of char;
20 tx,ty,tm:longint;
21 end;
22 var
23 q:array[1..maxq]of qnode;
24 h:array[0..bigprime-1]of longint;
25 table:array[1..maxh]of hnode;
26 f:array[1..maxq]of longint;
27 dep:array[1..maxq]of longint;
28 way:array[1..maxq]of char;
29 mumlet:set of char;
30 tempqnode:qnode;
31 x0,y0:longint;
32 wall:array[0..maxn*maxn-1,0..maxn*maxn-1]of longint;
33 map:array[0..maxn+1,0..maxn+1]of char;
34 m0x,m0y,ex,ey,n,i,j,w,elink,head,tail,y,l,k,v,u,
35 step,newx,newy,nowmx,nowmy:longint;
36 ans:array[1..maxa]of char;
37 flag,p,flag0,p0:boolean;
38 s:string;ch:char;
39 x:int64;
40 //h0:array[1..10000000]of longint;
41 x00:longint;
42 begin
43 assign(input,'mummy.in');
44 reset(input);
45 assign(output,'mummy.out');
46 rewrite(output);
47 mumlet:=['M','U','Y'];
48 readln(n);
49 q[1].tm:=0;
50 x:=1;
51 for i:=0 to n+1 do
52 begin
53 for j:=0 to n+1 do
54 begin
55 read(ch);
56 map[i,j]:=ch;
57 if ch='T'
58 then begin
59 q[1].tx:=i;
60 q[1].ty:=j;
61 x:=x*q[1].tx*q[1].ty;
62 end;
63 if ch='D'
64 then begin
65 ex:=i;
66 ey:=j;
67 end;
68 if ch in mumlet
69 then begin
70 inc(q[1].tm);
71 q[1].mx[q[1].tm]:=i;
72 q[1].my[q[1].tm]:=j;
73 x:=x*i*j;
74 end;
75 end;
76 readln;
77 end;
78 readln(w);
79 for i:=1 to w do
80 begin
81 readln(x0,y0);
82 wall[x0,y0]:=1;
83 wall[y0,x0]:=1;
84 end;
85 for i:=1 to q[1].tm do
86 begin
87 readln(s);
88 delete(s,1,6);
89 l:=length(s);
90 for j:=1 to q[1].tm do
91 if map[q[1].mx[j]][q[1].my[j]]=s[1]
92 then begin
93 q[1].mk[j]:=s[l];
94 break;
95 end;
96 end;
97 head:=1;
98 tail:=1;
99 elink:=0;
100 u:=h[x mod bigprime];
101 if h[x mod bigprime]=0
102 then begin
103 inc(elink);
104 h[x mod bigprime]:=elink;
105 table[elink].addr:=tail;
106 table[elink].next:=0;
107 end
108 else begin
109 inc(elink);
110 table[elink].addr:=tail;
111 table[elink].next:=table[h[x mod bigprime]].next;
112 table[h[x mod bigprime]].next:=elink;
113 end;
114 while head<=tail do
115 begin
116 for l:=1 to 5 do
117 begin
118 newx:=q[head].tx+dx[l];
119 newy:=q[head].ty+dy[l];
120 {if (head=58)and(l=5)
121 then l:=l;
122 if (q[head].tx=2)and(q[head].ty=4)
123 and(q[head].mx[1]=3)and(q[head].my[1]=3)
124 and(q[head].tm=1)
125 then l:=l;}
126 if wall[(newx-1)*n+newy-1][(q[head].tx-1)*n+q[head].ty-1]=1
127 then continue;
128 if map[newx][newy]='X' then continue;
129 if map[newx][newy]='D'
130 then begin
131 v:=head;
132 i:=0;
133 while v<>0 do
134 begin
135 v:=f[v];
136 if v=0 then break;
137 inc(i);
138 ans[i]:=way[v];
139 //WRITELN(Q[V].TX,' ',Q[V].TY);
140 end;
141 for j:=1 to i div 2 do
142 begin
143 ch:=ans[j];
144 ans[j]:=ans[i-j +1];
145 ans[i-j +1]:=ch;
146 end;
147 for j:=2 to i do
148 write(ans[j]);
149 write(way[head]);
150 case l of
151 1:writeln('D');
152 2:writeln('R');
153 3:writeln('U');
154 4:writeln('L');
155 5:writeln('S');
156 end;
157 close(input);
158 close(output);
159 //Mummies,you will lose the games forever!
160 halt;
161 end;
162 flag:=true;
163 tempqnode.tm:=0;
164 for k:=1 to q[head].tm do
165 begin
166 nowmx:=q[head].mx[k];
167 nowmy:=q[head].my[k];
168 m0x:=nowmx;
169 m0y:=nowmy;
170 case q[head].mk[k] of
171 'R': begin
172 step:=2;
173 flag0:=true;
174 while (step>0)and(flag0) do
175 begin
176 p0:=false;
177 while (nowmx<>newx)and(step>0)
178 and(wall[(nowmx-1)*n+nowmy-1]
179 [(nowmx+(newx-m0x)div(abs(newx-m0x))-1)*n+nowmy-1]<>1) do
180 begin
181 p0:=true;
182 m0y:=nowmy;
183 m0x:=nowmx;
184 dec(step);
185 nowmx:=nowmx+(newx-m0x)div(abs(newx-m0x));
186 end;
187 while (nowmy<>newy)and(step>0)
188 and(wall[(nowmx-1)*n+nowmy-1]
189 [(nowmx-1)*n+nowmy+(newy-m0y)div(abs(newy-m0y))-1]<>1) do
190 begin
191 p0:=true;
192 m0y:=nowmy;
193 m0x:=nowmx;
194 dec(step);
195 nowmy:=nowmy+(newy-m0y)div(abs(newy-m0y));
196 end;
197 if p0=false then flag0:=false;
198 end;
199 end;
200 'L': begin
201 step:=2;
202 flag0:=true;
203 while (step>0)and(flag0) do
204 begin
205 p0:=false;
206 while (nowmy<>newy)and(step>0)
207 and(wall[(nowmx-1)*n+nowmy-1]
208 [(nowmx-1)*n+nowmy+(newy-m0y)div(abs(newy-m0y))-1]<>1) do
209 begin
210 m0y:=nowmy;
211 m0x:=nowmx;
212 dec(step);
213 nowmy:=nowmy+(newy-m0y)div(abs(newy-m0y));
214 p0:=true;
215 end;
216 while (nowmx<>newx)and(step>0)
217 and(wall[(nowmx-1)*n+nowmy-1]
218 [(nowmx+(newx-m0x)div(abs(newx-m0x))-1)*n+nowmy-1]<>1) do
219 begin
220 m0y:=nowmy;
221 m0x:=nowmx;
222 dec(step);
223 nowmx:=nowmx+(newx-m0x)div(abs(newx-m0x));
224 p0:=true;
225 end;
226 if p0=false then flag0:=false;
227 end;
228 end;
229 end;
230 if (nowmx=newx)and(nowmy=newy) then begin flag:=false; break; end;
231 p:=false;
232 for i:=1 to k-1 do
233 if (tempqnode.mx[i]=nowmx)and(tempqnode.my[i]=nowmy)
234 then begin p:=true; break; end;
235 if p then continue;
236 inc(tempqnode.tm);
237 {if tempqnode.tm>q[head].tm
238 then l:=l;}
239 tempqnode.mx[tempqnode.tm]:=nowmx;
240 tempqnode.my[tempqnode.tm]:=nowmy;
241 tempqnode.mk[tempqnode.tm]:=q[head].mk[k];
242 end;
243 if flag=false then continue;
244 flag:=true;
245 tempqnode.tx:=newx;
246 tempqnode.ty:=newy;
247 x:=tempqnode.tx*tempqnode.ty;
248 for i:=1 to tempqnode.tm do
249 x:=x*tempqnode.mx[i]*tempqnode.my[i];
250 for i:=tempqnode.tm+1 to maxm do
251 begin
252 tempqnode.mx[i]:=0;
253 tempqnode.my[i]:=0;
254 end;
255 u:=h[x mod bigprime];
256 if u<>0
257 then begin
258 p:=true;
259 p:=p and((q[table[u].addr].tx=tempqnode.tx)
260 and(q[table[u].addr].ty=tempqnode.ty));
261 for i:=1 to maxm do
262 p:=p and((q[table[u].addr].mx[i]=tempqnode.mx[i])
263 and(q[table[u].addr].my[i]=tempqnode.my[i]));
264 if p=true then continue;
265 end;
266 while u<>0 do
267 begin
268 u:=table[u].next;
269 if u=0 then break;
270 p:=true;
271 p:=p and((q[table[u].addr].tx=tempqnode.tx)
272 and(q[table[u].addr].ty=tempqnode.ty));
273 for i:=1 to maxm do
274 p:=p and((q[table[u].addr].mx[i]=tempqnode.mx[i])
275 and(q[table[u].addr].my[i]=tempqnode.my[i]));
276 if p=true then begin flag:=false; break; end;
277 end;
278 if flag=false then continue;
279 x00:=0;
280 inc(tail);
281 q[tail].tx:=newx;
282 q[tail].ty:=newy;
283 q[tail].tm:=tempqnode.tm;
284 {x00:=x00*10+newx;
285 x00:=x00*10+newy;
286 x00:=x00*10+tempqnode.tm;}
287 for i:=1 to q[tail].tm do
288 begin
289 q[tail].mx[i]:=tempqnode.mx[i];
290 q[tail].my[i]:=tempqnode.my[i];
291 q[tail].mk[i]:=tempqnode.mk[i];
292 {x00:=x00*10+tempqnode.mx[i];
293 x00:=x00*10+tempqnode.my[i];}
294 end;
295 {if h0[x00]=1
296 then l:=l
297 else h0[x00]:=1;}
298 case l of
299 1:way[tail]:='D';
300 2:way[tail]:='R';
301 3:way[tail]:='U';
302 4:way[tail]:='L';
303 5:way[tail]:='S';
304 end;
305 f[tail]:=head;
306 dep[tail]:=dep[head]+1;
307 if h[x mod bigprime]=0
308 then begin
309 inc(elink);
310 h[x mod bigprime]:=elink;
311 table[elink].addr:=tail;
312 table[elink].next:=0;
313 end
314 else begin
315 inc(elink);
316 table[elink].addr:=tail;
317 table[elink].next:=table[h[x mod bigprime]].next;
318 table[h[x mod bigprime]].next:=elink;
319 end;
320 end;
321 inc(head);
322 end;
323 {Oh,Fuck,there must be an RP problem!}
324 close(input);
325 close(output);
326 end.
327 //Mummies,you will lose the games forever!
328
?
?
這個讀入還是比較繁瑣的
正在考慮好的方法
還準備加上鐵門鑰匙之類
?
BOB HAN原創 轉載請注明出處
轉載于:https://www.cnblogs.com/Booble/archive/2010/08/21/1805392.html
總結
以上是生活随笔為你收集整理的[Mummy Maze] 宽度优先搜索的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 我的Flex4征程
- 下一篇： WinDbg配置与下载