深度、廣度和雙向搜索優(yōu)化及其應(yīng)用-資料下載頁(yè)
2025-08-15 22:43本頁(yè)面
【正文】 error!39。)。halt。end。 ? a[y,x]:=1。 ? find(y,x,2)。 ? if cont=0 then writeln(39。No answer!39。) else write(39。The End!39。)。 ? readln。 ? end. ? 在 n*n的正方形中放置長(zhǎng)為 2,寬為 1的長(zhǎng)條塊 ,問(wèn)放置方案如何 ? const n=4。 ? var k,u,v,result:integer。 ? a:array[1..n,1..n]of char。 ? procedure printf。 {輸出 } ? begin ? result:=result+1。 {方案總數(shù)加 1} ? writeln(39。 39。,result,39。 39。)。 ? for v:=1 to n do begin ? for u:=1 to n do write(a[u,v])。 writeln end。 writeln。 ? end。 ? begin {主程序 } ? fillchar(a,sizeof(a),39。 39。)。 {記錄放置情況的字符數(shù)組 ,初始值為空格 } ? result:=0。 k:=0。 {k記錄已放的塊數(shù) ,如果 k=n*n/2,則說(shuō)明已放滿 } ? try。 {每找到一個(gè)空位置 ,把長(zhǎng)條塊分別橫放和豎放試驗(yàn) } ? end. ? procedure try。 {填放長(zhǎng)條塊 } ? var i,j,x,y:integer。 full:boolean。 ? begin ? full:=true。 ? if ktrunc(n*n/2) then full:=false。{測(cè)試是否已放滿 } ? if full then printf。 {放滿則可輸出 } ? if not full then begin {未滿 } ? x:=0。y:=1。 {以下先搜索未放置的第一個(gè)空位置 } ? repeat ? x:=x+1。 ? if xn then begin x:=1。y:=y+1 end ? until a[x,y]=39。 39。 ? {找到后 ,分兩種情況討論 } ? if a[x+1,y]=39。 39。 then begin {第一種情況 :橫向放置長(zhǎng)條塊 } ? k:=k+1。 {記錄已放的長(zhǎng)條數(shù) } ? a[x,y]:=chr(k+ord(39。@39。))。 {放置 } ? a[x+1,y]:=chr(k+ord(39。@39。))。 ? try。 {遞歸找下一個(gè)空位置放 } ? k:=k1。 ? a[x,y]:=39。 39。 {回溯 ,恢復(fù)原狀 } ? a[x+1,y]:=39。 39。 ? end。 ? if a[x,y+1]=39。 39。 then begin {第二種情況 :豎向放置長(zhǎng)條塊 } ? k:=k+1。 {記錄已放的長(zhǎng)條數(shù) } ? a[x,y]:=chr(k+ord(39。039。))。 {放置 } ? a[x,y+1]:=chr(k+ord(39。039。))。 ? try。 {遞歸找下一個(gè)空位置放 } ? k:=k1。 ? a[x,y]:=39。 39。 {回溯 ,恢復(fù)原狀 } ? a[x,y+1]:=39。 39。 ? end。 ? end。 ? end。 ? 找迷宮的最短路徑 ? uses crt。 ? const ? migong:array [1..5,1..5] of integer=((0,0,1,0,0), (0,1,0,0,1), ? (0,0,0,0,0), (0,1,0,0,0), (1,0,0,1,0))。 ? {迷宮數(shù)組 } ? fangxiang:array [1..4,1..2] of 1..1=((1,0),(0,1),(1,0),(0,1))。 ? {方向增量數(shù)組 } ? type node=record ? lastx:integer。 {上一位置坐標(biāo) } ? lasty:integer。 ? nowx:integer。 {當(dāng)前位置坐標(biāo) } ? nowy:integer。 ? pre:byte。 {本結(jié)點(diǎn)由哪一步擴(kuò)展而來(lái) } ? dep:byte。 {本結(jié)點(diǎn)是走到第幾步產(chǎn)生的 } ? end。 ? var ? lujing:array[1..25] of node。 {記錄走法數(shù)組 } ? closed,open,x,y,r:integer。 ? procedure output。 ? var i,j:integer。 ? begin ? for i:=1 to 5 do begin ? for j:=1 to 5 do ? write(migong[i,j]:4)。 writeln。end。 ? i:=open。 ? repeat ? with lujing[i] do ? write(nowy:2,39。,39。,nowx:2,39。 39。)。 ? i:=lujing[i].pre。 ? until lujing[i].pre=0。 ? with lujing[i] do ? write(nowy:2,39。,39。,nowx:2)。 ? end。 ? begin ? clrscr。 ? with lujing[1] do begin {初始化第一步 } ? lastx:=0。 lasty:=0。 nowx:=1。nowy:=1。pre:=0。dep:=1。end。 ? closed:=0。open:=1。migong[1,1]:=1。 ? repeat ? inc(closed)。 {隊(duì)列首指針加 1,取下一結(jié)點(diǎn) } ? for r:=1 to 4 do begin {以 4個(gè)方向擴(kuò)展當(dāng)前結(jié)點(diǎn) } ? x:=lujing[closed].nowx+fangxiang[r,1]。 {擴(kuò)展形成新的坐標(biāo)值 } ? y:=lujing[closed].nowy+fangxiang[r,2]。 ? if not ((x5)or(y5) or (x1) or (y1) or (migong[y,x]0)) then begin ? {未出界 ,未走過(guò)則可視為新的結(jié)點(diǎn) } ? inc(open)。 {隊(duì)列尾指針加 1} ? with lujing[open] do begin {記錄新的結(jié)點(diǎn)數(shù)據(jù) } ? nowx:=x。 nowy:=y。 ? lastx:=lujing[closed].nowx。{新結(jié)點(diǎn)由哪個(gè)坐標(biāo)擴(kuò)展而來(lái) } ? lasty:=lujing[closed].nowy。 ? dep:=lujing[closed].dep+1。 {新結(jié)點(diǎn)走到第幾步 } ? pre:=closed。 {新結(jié)點(diǎn)由哪個(gè)結(jié)點(diǎn)擴(kuò)展而來(lái) } ? end。 ? migong[y,x]:=lujing[closed].dep+1。 {當(dāng)前結(jié)點(diǎn)的覆蓋范圍 } ? if (x=5) and (y=5) then begin {輸出找到的第一種方案 } ? writeln(39。ok,thats all right39。)。output。halt。end。 ? end。 ? end。 ? until closed=open。 {直到首指針大于等于尾指針 ,即所有結(jié)點(diǎn)已擴(kuò)展完 } ? end.
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1