算法分析編程學(xué)到現(xiàn)在才真正到了戲

1、算法分析編程學(xué)到現(xiàn)在才真正到了戲肉部分，從這里往下學(xué)，你才知道什么叫做博大精深。今天我們要啃的這塊硬骨頭叫做深度優(yōu)先搜索法。 首先我們來想象一只老鼠，在一座不見天日的迷宮內(nèi)，老鼠在入口處進(jìn)去，要從出 口出來。那老鼠會怎么走？當(dāng)然是這樣的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意選 擇其中的一個繼續(xù)往下走，如果遇到死胡同，就退回到最近的一個分叉路口，選擇另一條道路再走下去，如果 遇到了出口，老鼠的旅途就算結(jié)束了。深度優(yōu)先搜索法的基本原則就是這樣：按照某種條件往前試探搜索，如 果前進(jìn)中遭到失?。ㄕ缋鲜笥龅剿篮﹦t退回頭另選通路繼續(xù)搜索，直到找到條件的目標(biāo)為止。實現(xiàn)這一算法，我們

2、要用到編程的另一大利器-遞歸。遞歸是一個很抽象的概念， 但是在日常生活中，我們還是能夠看到的。拿兩面鏡子來，把他們面對著面，你會看到什么？你會看到鏡子中 有無數(shù)個鏡子？怎么回事？A鏡子中有B鏡子的象，B鏡子中有A鏡子的象，A鏡子的象就是A鏡子本身的真實寫 照，也就是說A鏡子的象包括了A鏡子，還有B鏡子在A鏡子中的象好累啊，又煩又繞口，還不好理 解。換成計算機(jī)語言就是A調(diào)用B，而B又調(diào)用A，這樣間接的，A就調(diào)用了A本身，這實現(xiàn)了一個重復(fù)的功能。再 舉一個例子；從前有座山，山里有座廟，廟里有個老和尚，老和尚在講故事，講什么呢？講：從前有座山，山 里有座廟，廟里有個老和尚，老和尚在講故事，講什么呢？

3、講：從前有座山，山里有座廟，廟里有個老和尚， 老和尚在講故事，講什么呢？講：。好家伙，這樣講到世界末日還講不玩，老和尚講的故事實際上就 是前面的故事情節(jié)，這樣不斷地調(diào)用程序本身，就形成了遞歸。 萬一這個故事中的某一個老和尚看這個故事不 順眼，就把他要講的故事?lián)Q成：“你有完沒完??！”，這樣，整個故事也就嘎然而止了。我們編程就要注意這 一點，在適當(dāng)?shù)臅r候，就必須要有一個這樣的和尚挺身而出，把整個故事給停下來，或者使他不再往深一層次 搜索，要不，我們的遞歸就會因計算機(jī)存儲容量的限制而被迫溢出，切記，切記。 我們把遞歸思想運(yùn)用到上面的迷宮中，記老鼠現(xiàn)在所在的位置是(x,y),那它現(xiàn)在有 前后左右4個方

4、向可以走，分別是(x+1,y),(x-1,y),(x,y+1),(x,y-1),其中一個方向是它來時的路，我們先不 考慮，我們就分別嘗試其他三個方向，如果某個方向是路而不是墻的話，老鼠就向那個方向邁出一步。在新的 位置上，我們又可以重復(fù)前面的步驟。老鼠走到了死胡同又是怎么回事？就是除了來時的路，其他3個方向都是 墻，這時這條路就走到了盡頭，無法再向深一層發(fā)展，我們就應(yīng)該沿來時的路回去，嘗試另外的方向。 例：八皇后問題：在標(biāo)準(zhǔn)國際象棋的棋盤上（8*8格）準(zhǔn)備放置8只皇后，我們知 道，國際象棋中皇后的威力是最大的，她既可以橫走豎走，還可以斜著走，遇到擋在她前進(jìn)路線上的敵人，她 就可以吃掉對手。要求

5、在棋盤上安放8只皇后，使她們彼此互相都不能吃到對方，求皇后的放法。 這是一道很經(jīng)典的題目了，我們先要明確一下思路，如何運(yùn)用深度優(yōu)先搜索法，完 成這道題目。我們先建立一個8*8格的棋盤，在棋盤的第一行的任意位置安放一只皇后。緊接著，我們就來放 第二行，第二行的安放就要受一些限制了，因為與第一行的皇后在同一豎行或同一對角線的位置上是不能安放 皇后的，接下來是第三行，或許我們會遇到這種情況，在擺到某一行的時候，無論皇后擺放在什么位 置，她都會被其他行的皇后吃掉，這說明什么呢？這說明，我們前面的擺放是失敗的，也就是說，按照前面 的皇后的擺放方法，我們不可能得到正確的解。那這時怎么辦？改啊，我們回到上一

6、行，把原先我們擺好的 皇后換另外一個位置，接著再回過頭擺這一行，如果這樣還不行或者上一行的皇后只有一個位置可放，那怎 么辦？我們回到上一行的上一行，這和老鼠碰了壁就回頭是一個意思。就這樣的不斷的嘗試，修正，嘗試修 正，我們最終會得到正確的結(jié)論的。 參考程序 program queen;8皇后問題參考程序 const n=8; var a,b:array 1.n of integer;數(shù)組a存放解：ai表示第i個皇后放在第ai列； c:array 1-n,n-1 of integer; d:array 2.n+n of integer;數(shù)組b，c，d表示棋盤的當(dāng)前情況：bk為1表示第k行已被占領(lǐng)

7、為0表示為空；c、d表示對角線 k:integer; procedure print;打印結(jié)果 var j:integer; begin for j:=1 to n do write(aj:4); writeln; end; procedrue try(i:integer); 遞歸搜索解 var j:integer;每個皇后的可放置位置。注意：一定要在過程中定義；否則當(dāng)遞歸時會覆蓋掉它的值，不能得到正確結(jié)果 begin for j:=1 to n do begin if (bj=0) and (ci-j=0) and (di+j=0) then檢查位置是否合法 begin ai:=j;置第i個

8、皇后的位置是第j行 bj:=1;宣布占領(lǐng)行、對角線 ci-j:=1; di+j:=1; if i<n then try(i+1) else print;如果末達(dá)目標(biāo)則放置下一皇后，否則打印結(jié)果 bj:=0;清空被占行、對角線，回溯 ci-j:=0; di+j:=0; end; end; end; begin for k:=1 to n do bk:=0;初始化數(shù)據(jù) for k:=1-n to n-1 do ck:=0; for k:=2 to n+n do dk:=0; try(1); end. 習(xí)題 1、完成上述老鼠走迷宮問題。 那么深度優(yōu)先搜索與廣度優(yōu)先搜索算法有何區(qū)別呢？ 通常深度

9、優(yōu)先搜索法不全部保留結(jié)點，擴(kuò)展完的結(jié)點從數(shù)據(jù)庫中彈出刪去，這樣，一般在數(shù)據(jù)庫中存儲的結(jié)點數(shù)就是深度值，因此它占用空間較少。所以，當(dāng)搜索樹的結(jié)點較多，用其它方法易產(chǎn)生內(nèi)存溢出時，深度優(yōu)先搜索不失為一種有效的求解方法。 廣度優(yōu)先搜索算法，一般需存儲產(chǎn)生的所有結(jié)點，占用的存儲空間要比深度優(yōu)先搜索大得多，因此，程序設(shè)計中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。但廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運(yùn)行速度比深度優(yōu)先搜索要快些。    將從迷宮入口到各點的最短路近的集合看作一棵樹。用廣度遍歷  的方法即可找到出口的最短路近。本程序

10、算法思想來源于求圖上一點  到其余各點最短路近的Dijkstra算法。 /* 迷宮探路III（最短路徑）*/* DIJKSTRAMAZE.C */* 2003-8-26 */#include <stdlib.h>#include <time.h>#include <math.h>#include <stdio.h>#include <graphics.h>#define N 22#define M 22int bgMN;int aaMN;struct pace    int

11、pre;    int x;    int y;    int ri;    int rj;roadM*N;struct pace bestroadM*N;void makebg(int,int);void drawbg(int,int,int,int,int,int);void drawman(int,int,int);void rect(int,int,int,int);void main()/* main()開始 */int step=20;int len=10;int

12、 size=20;int x=0,y=0;int i=0,j=0;int gdriver=DETECT,gmode;char ch;int direc;int routelen=0;int dj=-1,1,0,0;int di=0,0,-1,1;int begin;int end;int k;int t;int num;int suc;int cnt;int x0;int y0;int le;int tmp;makebg(M,N);/*  registerbgidriver(EGAVGA_driver); initgraph(&gdriver,&g

13、mode,"c:turboc2");*/ initgraph(&gdriver,&gmode,"c:tc20bgi"); cleardevice();setwritemode(XOR_PUT);settextstyle(1,0,3);setcolor(GREEN);outtextxy(100,180,"DIJKSTRA MAZE");setcolor(BLUE);setfillstyle(LINE_FILL,BLUE);/*drawbg(bg,M,N,size,0,0);*/drawbg(aa,M,N,siz

14、e,0,0);setcolor(WHITE);x+=len;y+=len;drawman(x,y,len);x0=x;y0=y;/* 電腦控制 */i=j=0;aa00=1;begin=0;end=0;road0.ri=0;road0.rj=0;road0.x=x0;road0.y=y0;road0.pre=-1;le=1;suc=0;while(!suc)cnt=0;le+;for(k=begin;k<=end;k+)    for(t=0;t<4;t+)        x=roa

15、dk.x+djt*step;        y=roadk.y+dit*step ;        i=roadk.ri+dit;        j=roadk.rj+djt;        if(i<M&&i>=0&&j<N&&j>=0&

16、&aaij=0)            cnt+;            aaij=le;            roadend+cnt.pre=k;         &#

17、160;  roadend+cnt.x=x;            roadend+cnt.y=y;            roadend+cnt.ri=i;            roadend+cnt.rj=j;   

18、0;        if(i=N-1&&j=M-1)                suc=1;                break;      &

19、#160;                     if(suc)break;begin=end+1;end=end+cnt;/* output */i=end;j=0;while(i!=-1)    bestroadj.x=roadi.x;    bestroadj.y=roadi.y;    bestroadj.ri=roadi.ri

20、;    bestroadj.rj=roadi.rj;    i=roadi.pre;    j+;for(i=0;i<j/2;i+)    tmp=bestroadi.x;    bestroadi.x=bestroadj-1-i.x;    bestroadj-1-i.x=tmp;    tmp=bestroadi.y;    bestroadi.

21、y=bestroadj-1-i.y;    bestroadj-1-i.y=tmp;getch();drawman(x0,y0,len);for(i=0;i<j;i+)    drawman(bestroadi.x,bestroadi.y,len);    delay(80000);    drawman(bestroadi.x,bestroadi.y,len);i-;drawman(bestroadi.y,bestroadi.x,len);getch();closeg

22、raph();/* main()結(jié)束 */* 繪制小人 */void drawman(int x,int y,int len)    int r=len/4;    rect(x-r,y-len,x+r,y-len+2*r);    line(x,y-len+2*r,x,y);    line(x-len,y,x+len,y);    line(x,y,x-len,y+len);    line(x,y,x+len,

23、y+len);/* 繪制迷宮地圖 */void drawbg(int bgN,int a,int b,int size,int x,int y)    int startx=x;    int i,j;    for(i=0;i<a;i+)        for(j=0;j<b;j+)            if(b

24、gij=-1)                rect(x,y,x+size-1,y+size-1);            x+=size;                x=startx;

25、0;       y+=size;        rectangle(0,0,size*b,size*a);    line(0,0,size,0);line(0,0,0,size);    line(size*b,size*(a-1),size*b,size*a);    line(size*(b-1),size*a,size*b,size*a);/* 繪制實心矩形 */void re

26、ct(int x0,int y0,int x1,int y1)    int i,j;    for(i=x0;i<=x1;i+)        line(i,y0,i,y1);/* 隨機(jī)生成代表迷宮地圖的數(shù)組  */void makebg(int a,int b)    int i,j;    int ran;    int direc;/* 初始化迷宮地圖&

27、#160; */    for(i=0;i<a;i+)        for(j=0;j<b;j+)            bgij=1;/* 隨機(jī)生成迷宮通路  */    randomize();    i=j=0;direc=2;    while(1) 

28、60;      bgij=0;        if(i>=M-1&&j>=N-1)break;        ran=(int)rand()*4;        if(ran<1)          &#

29、160; if(direc!=1&&i<a-1)                i+;                direc=3;             

30、;                   else if(ran<2)            if(direc!=2&&j>0)              

31、0; j-;                direc=0;                            else if(ran<3)    &

32、#160;       if(direc!=3&&i>0)                i-;                direc=1;      &

33、#160;                     else             if(direc!=0&&j<b-1)             

34、0;  j+;                direc=2;                                  

35、   /* 隨機(jī)生成迷宮其余部分  */    for(i=0;i<a;i+)        for(j=0;j<b;j+)            if(bgij=1)               

36、 ran=(int)rand()*10;                if(ran<5)bgij=0;                for(i=0;i<a;i+)        for(j=0;j<b;j+) 

37、;           if(bgij=1)aaij=-1;            else aaij=0;    迷宮探路IV(遞歸算法)/* 迷宮探路（recursive）*/* recursivemaze.c */* 2003-10-16 */#include <stdlib.h>#include <time.h>#includ

38、e <math.h>#include <stdio.h>#include <graphics.h>#define N 22#define M 22#define MAXLEN M*Nint bgMN;int aaMN;struct pace    int dir;    int ri;    int rj;roadMAXLEN;int length=0;int dj=1,0,-1,0;int di=0,1,0,-1;void makebg(int,int);void d

39、rawbg(int,int,int,int,int,int);void drawman(int,int,int);void rect(int,int,int,int);int go(int ,int ,int);void main()/* main()開始 */int step=20;int len=10;int size=20;int x=0,y=0;int i=0,j=0;int gdriver=DETECT,gmode;makebg(M,N);/* registerbgidriver(EGAVGA_driver);initgraph(&gdriver,&gmode,&qu

40、ot;c:turboc2");*/initgraph(&gdriver,&gmode,"c:tc20bgi"); cleardevice();setwritemode(XOR_PUT);settextstyle(1,0,3);setcolor(GREEN);outtextxy(100,180,"RECURSIVE MAZE");setcolor(BLUE);setfillstyle(LINE_FILL,BLUE);/*drawbg(bg,M,N,size,0,0);*/drawbg(aa,M,N,size,0,0);setcol

41、or(WHITE);x+=len;y+=len;drawman(x,y,len);/* 電腦控制 */aa00=1;road0.ri=0;road0.rj=0;road0.dir=0;go(0,0,0);/* output */getch();drawman(x,y,len);for(i=0;i<=length;i+)    drawman(x+roadi.rj*step,y+roadi.ri*step,len);    delay(80000);    drawman(x+roadi.rj*ste

42、p,y+roadi.ri*step,len);i-;drawman(x+roadi.rj*step,y+roadi.ri*step,len);getch();closegraph();/* main()結(jié)束 */* 繪制小人 */void drawman(int x,int y,int len)    int r=len/4;    rect(x-r,y-len,x+r,y-len+2*r);    line(x,y-len+2*r,x,y);    line(x-len,y

43、,x+len,y);    line(x,y,x-len,y+len);    line(x,y,x+len,y+len);/* 繪制迷宮地圖 */void drawbg(int bgN,int a,int b,int size,int x,int y)    int startx=x;    int i,j;    for(i=0;i<a;i+)        for(

44、j=0;j<b;j+)            if(bgij=-1)                rect(x,y,x+size-1,y+size-1);            x+=size;  &#

45、160;             x=startx;        y+=size;        rectangle(0,0,size*b,size*a);    line(0,0,size,0);line(0,0,0,size);    line(size*b,size*(a-1),size*b

46、,size*a);    line(size*(b-1),size*a,size*b,size*a);/* 繪制實心矩形 */void rect(int x0,int y0,int x1,int y1)    int i,j;    for(i=x0;i<=x1;i+)        line(i,y0,i,y1);/* 隨機(jī)生成代表迷宮地圖的數(shù)組  */void makebg(int a,int b) 

47、60;  int i,j;    int ran;    int direc;/* 初始化迷宮地圖  */    for(i=0;i<a;i+)        for(j=0;j<b;j+)            bgij=1;/* 隨機(jī)生成迷宮通路  */  

48、60; randomize();    i=j=0;direc=2;    while(1)        bgij=0;        if(i>=M-1&&j>=N-1)break;        ran=(int)rand()*4;     &#

49、160;  if(ran<1)            if(direc!=1&&i<a-1)                i+;              &#

50、160; direc=3;                                else if(ran<2)            if(direc!=2&&j>0)

51、60;               j-;                direc=0;                   

52、        else if(ran<3)            if(direc!=3&&i>0)                i-;        

53、60;       direc=1;                            else             if(direc!=0&&j<b

54、-1)                j+;                direc=2;                  &

55、#160;                  /* 隨機(jī)生成迷宮其余部分  */    for(i=0;i<a;i+)        for(j=0;j<b;j+)            if(bgij=1) 

56、;               ran=(int)rand()*10;                if(ran<5)bgij=0;               

57、 for(i=0;i<a;i+)        for(j=0;j<b;j+)            if(bgij=1)aaij=-1;            else aaij=0;    int go(int i,int j,int dir) 

58、0;  if(length=-1)return -1;    if(i=M-1&&j=N-1)return 1;    if(dir=4)        length-;        roadlength.dir+;        go(roadlength.ri,roadlength.rj,road

59、length.dir);        else        if(aai+didir>j+djdir>=0            &&i+didir>=0&&i+didir<M          &#

60、160; &&j+djdir>=0&&j+djdir<N)            length+;            roadlength.ri=i+didir;            roadlength.rj=j+dj

61、dir;            roadlength.dir=0;            aaroadlength.riroadlength.rj=length+1;            go(roadlength.ri,roadlength.rj,roadlengt

62、h.dir);                else            dir+;            go(i,j,dir);         

63、60;        對迷宮探路做了一點改進(jìn)。小人在行走過程中不走回頭路,即不重復(fù)經(jīng)過同一點。                      /* crazymaze.c*/* 2003-8-26 */#include <stdlib.h>#include <time.h>#include <math.h>

64、#include <stdio.h>#include <graphics.h>#define N 22#define M 22#define MAXLEN 200;int bgMN;struct square    int x;    int y;    int direc;p200;void makebg(int,int);void drawbg(int,int,int,int,int,int);void drawman(int,int,int);void rect(int,in

65、t,int,int);void main()/* main()開始 */int step=20;int len=10;int size=20;int x=0,y=0,x0=0,y0=0;int i=0,j=0,k=0,count=0;int gdriver=DETECT,gmode;char ch;int direc;makebg(M,N);/*  registerbgidriver(EGAVGA_driver); initgraph(&gdriver,&gmode,"c:turboc2");*/initgraph(&gdrive

66、r,&gmode,"c:tc20bgi");cleardevice();setwritemode(XOR_PUT);settextstyle(1,0,3);setcolor(GREEN);outtextxy(100,180,"Press <Q> to quit");setcolor(BLUE);setfillstyle(LINE_FILL,BLUE);drawbg(bg,M,N,size,0,0);setcolor(GREEN);outtextxy(60,120,"PRESS KEY <1> :YOU ,&quo

67、t;);outtextxy(70,150,"OTHER KEY :AUTOMATIC");setcolor(WHITE);x+=len;y+=len;drawman(x,y,len);x0=x;y0=y;if(ch=getch()='1')/* 人工控制 */while(ch=getch()!='q')  delay(800);  drawman(x,y,len);  switch(ch)    case 'a':    

68、60;   if(j>0&&bgij-1=0)            if(x>step)x-=step;j-;                break;    case 's':      &

69、#160; if(i<M-1&&bgi+1j=0)            if(y<479-step)y+=step;i+;                break;    case 'd':       

70、; if(j<N-1&&bgij+1=0)            if(x<639-step)x+=step;j+;                break;    case 'w':        if

71、(i>0&&bgi-1j=0)            if(y>step)y-=step;i-;                break;    default :break;    drawman(x,y,len); if(i>=M-1&&am

72、p;j>=N-1)    settextstyle(4,0,3);    setcolor(RED);    outtextxy(150,260,"YOU WIN!");    setcolor(WHITE); closegraph();/* 人工控制結(jié)束 */else/* 電腦控制 */* direc表示上一步運(yùn)動方向 */* 并表示下一步運(yùn)動方向 */* 03分別表示 西、北、東、南 */direc=2;i=j=0;k=0;while(i<

73、M-1|j<N-1)    switch(direc)    case 0:        /* 以3,0,1,2的次序嘗試 */         if(i<M-1&&bgi+1j=0)            y+=step;i+;  

74、60;         direc=3;                else if(j>0&&bgij-1=0)            x-=step;j-;       &

75、#160;    direc=0;                else if(i>0&&bgi-1j=0)            y-=step;i-;            dire

76、c=1;                else             x+=step;j+;            direc=2;         

77、60;      pk.x=x;        pk.y=y;        pk.direc=direc;        if(k>0)            count=k-1;   

78、60;        while(count>=0            &&(pcount.x!=pk.x|pcount.y!=pk.y)            count-;         &

79、#160;  if(count>=0)                k=count;                pk.direc=direc;           &#

80、160;    i=(pk.y-len)/step;                j=(pk.x-len)/step;                          

81、0; k+;        break;    case 1:        if(j>0&&bgij-1=0)            x-=step;j-;            dir

82、ec=0;                else if(i>0&&bgi-1j=0)            y-=step;i-;            direc=1;    

83、;            else if(j<N-1&&bgij+1=0)            x+=step;j+;            direc=2;         

84、       else            y+=step;i+;            direc=3;                pk.x=x;  &

85、#160;     pk.y=y;        pk.direc=direc;        if(k>0)            count=k-1;            while(co

86、unt>=0            &&(pcount.x!=pk.x|pcount.y!=pk.y)            count-;            if(count>=0)    

87、60;           k=count;                pk.direc=direc;                i=(pk.y-len)/step;  &

88、#160;             j=(pk.x-len)/step;                            k+;        break

89、;    case 2:        if(i>0&&bgi-1j=0)            y-=step;i-;            direc=1;         

90、       else if(j<N-1&&bgij+1=0)            x+=step;j+;            direc=2;             &#

91、160;  else if(i<M-1&&bgi+1j=0)            y+=step;i+;            direc=3;                else  

92、0;          x-=step;j-;            direc=0;                pk.x=x;        pk.y=y;  &#

93、160;     pk.direc=direc;        if(k>0)            count=k-1;            while(count>=0       

94、     &&(pcount.x!=pk.x|pcount.y!=pk.y)            count-;            if(count>=0)             

95、   k=count;                pk.direc=direc;                i=(pk.y-len)/step;          

96、0;     j=(pk.x-len)/step;                            k+;        break;    case 3:    

97、    if(j<N-1&&bgij+1=0)            x+=step;j+;            direc=2;                else if(i<

98、;M-1&&bgi+1j=0)            y+=step;i+;            direc=3;                else if(j>0&&bgij-1=0) 

99、;           x-=step;j-;            direc=0;                else           &

100、#160; y-=step;i-;            direc=1;                pk.x=x;        pk.y=y;        pk.direc=direc; &

101、#160;      if(k>0)            count=k-1;            while(count>=0            &&(pcount.x!=pk.x|

102、pcount.y!=pk.y)            count-;            if(count>=0)                k=count;     

103、           pk.direc=direc;                i=(pk.y-len)/step;                j=(pk.x-len)/step; 

104、                           k+;        break;    default :break;            drawman(x0

105、,y0,len);    for(i=0;i<k-1;i+)                     drawman(pi.x,pi.y,len);         delay(80000);         dr

106、awman(pi.x,pi.y,len);        drawman(pi.x,pi.y,len);    /* printf("%6dn",k);    for(i=0;i<k;i+)         printf("%6dn",pk.y*N+pk.x);       

107、0; if(k+1)%10=0)printf("n");    */    getch();    closegraph();/* 電腦控制結(jié)束 */* main()結(jié)束 */* 繪制小人 */void drawman(int x,int y,int len)    int r=len/4;    rect(x-r,y-len,x+r,y-len+2*r);    line(x,y-len+2*r

108、,x,y);    line(x-len,y,x+len,y);    line(x,y,x-len,y+len);    line(x,y,x+len,y+len);/* 繪制迷宮地圖 */void drawbg(int bgN,int a,int b,int size,int x,int y)    int startx=x;    int i,j;    for(i=0;i<a;i+) 

109、0;      for(j=0;j<b;j+)            if(bgij=1)                rect(x,y,x+size-1,y+size-1);         

110、;   x+=size;                x=startx;        y+=size;        rectangle(0,0,size*b,size*a);    line(0,0,size,0);line(0,0,0,size);  

111、  line(size*b,size*(a-1),size*b,size*a);    line(size*(b-1),size*a,size*b,size*a);/* 繪制實心矩形 */void rect(int x0,int y0,int x1,int y1)    int i,j;    for(i=x0;i<=x1;i+)        line(i,y0,i,y1);/* 隨機(jī)生成代表迷宮地圖的數(shù)組 

112、 */void makebg(int a,int b)    int i,j;    int ran;    int direc;/* 初始化迷宮地圖  */    for(i=0;i<a;i+)        for(j=0;j<b;j+)            bgij=1;/* 隨機(jī)生成迷宮通路  */    rand