+Ȧ

c 的一些经典算法,满好的,适合初学者. 也可以当作小程序看,对初学者会很有帮助

/* 迷宫探路（recursive）*/
/* recursivemaze.c */
/* 2003-10-16 */
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <graphics.h>
#define N 22
#define M 22
#define MAXLEN M*N
int bg[M][N];
int aa[M][N];

struct pace{ /*定义结构体*/
    int dir;
    int ri;
    int rj;
}road[MAXLEN];

int length=0;
int dj[]={1,0,-1,0};
int di[]={0,1,0,-1};
void makebg(int,int);
void drawbg(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;
	int gdriver=DETECT,gmode;
	makebg(M,N);
	/* registerbgidriver(EGAVGA_driver);
	initgraph(&gdriver,&gmode,"c:\\turboc2");*/
	initgraph(&gdriver,&gmode,"c:\\tc20\\bgi"); 
	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);
	setcolor(WHITE);
	x+=len;y+=len;
	drawman(x,y,len);
	/* 电脑控制 */
	aa[0][0]=1;
	road[0].ri=0;
	road[0].rj=0;
	road[0].dir=0;
	go(0,0,0);
	/* output */
	getch();
	drawman(x,y,len);
	for(i=0;i<=length;i++)
		{
		drawman(x+road[i].rj*step,y+road[i].ri*step,len);
		delay(80000);
		drawman(x+road[i].rj*step,y+road[i].ri*step,len);
		}
	i--;
	drawman(x+road[i].rj*step,y+road[i].ri*step,len);
	getch();
	closegraph();
	printf("Press any key to quit!");
	getch();
}/* main()结束 */

/* 绘制小人 */
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,y+len);
}
/* 绘制迷宫地图 */
void drawbg(int bg[][N],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(bg[i][j]==-1)
                rect(x,y,x+size-1,y+size-1);
            x+=size;
        }
        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,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);
}
/* 随机生成代表迷宫地图的数组  */
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++)
            bg[i][j]=1;
/* 随机生成迷宫通路  */
    randomize();
    i=j=0;direc=2;
    while(1){
        bg[i][j]=0;
        if(i>=M-1&&j>=N-1)break;
        ran=(int)rand()*4;
        if(ran<1){
            if(direc!=1&&i<a-1){
                i++;
                direc=3;
            }
        }    
        else if(ran<2){
            if(direc!=2&&j>0){
                j--;
                direc=0;
            }
        }
        else if(ran<3){
            if(direc!=3&&i>0){
                i--;
                direc=1;
            }
        }
        else {
            if(direc!=0&&j<b-1){
                j++;
                direc=2;            
            }
        }
     }
/* 随机生成迷宫其余部分  */
    for(i=0;i<a;i++)
        for(j=0;j<b;j++)
            if(bg[i][j]==1){
                ran=(int)rand()*10;
                if(ran<5)bg[i][j]=0;
            }
    for(i=0;i<a;i++)
        for(j=0;j<b;j++){
            if(bg[i][j]==1)aa[i][j]=-1;
            else aa[i][j]=0;
    }
}
int go(int i,int j,int dir){
    if(length==-1)return -1;
    if(i==M-1&&j==N-1)return 1;
    if(dir==4){
        length--;
        road[length].dir++;
        go(road[length].ri,road[length].rj,road[length].dir);
    }
    else{
        if(aa[i+di[dir]][j+dj[dir]]==0  /*被我改动过，2004.10.23*/
            &&i+di[dir]>=0&&i+di[dir]<M
            &&j+dj[dir]>=0&&j+dj[dir]<N){
            length++;
            road[length].ri=i+di[dir];
            road[length].rj=j+dj[dir];
            road[length].dir=0;
            aa[road[length].ri][road[length].rj]=length+1;
            go(road[length].ri,road[length].rj,road[length].dir);
        }
        else{
            dir++;
            go(i,j,dir);
        }
    }
}