数据结构课程设计 - 迷宫(3)

bar（）函数输出矩形块，每个块的大小为12*12单位，块与块间距为3，如果数组元素值为0，则填充为白色，值为1显示填充为蓝色，一个数组元素对应一个矩形块。数组元素的下标为矩形块的中心坐标，利用两重循环语句可以完成迷宫图的显示。

3.5 FindWay（）系统自动探索

从下标（1，1）开始探索，依次按照右下、下、右、上、右上、左下、、左、左上的顺序前进，若该方向上的值为0，则前进一步，然后作相应的标记，表示该探索物在某一方向探索过，而在另一个方向上探索，若8个方向均已探索过，则不能再前进，需要沿着原来的路径回溯一步，然后重复上述过程直到出口。

判断8个方向的顺序前三个是判断右下、下、右、这样的话可以以最短的路径找到迷宫出口。

因为要回溯，所以实现的方法可以有两种；一种是非递归型方法，设置一个堆栈，记录所有走过的路径，前进时入栈，回溯时可以出栈；另一种是递归方法，不必设堆栈，但递归的方法其实就是栈的应用，只不过栈由系统安排，对用户是不可见的。本程序采用了后者实现。

在递归过程中凡是已经走过的路，做标记为1，防止来回徘徊而最终无法找到出口。由于走过的路数组元素要改变为1，为了8个方向的递归和回溯，所以做了一个函数WayCopy（）把旧迷宫数组拷贝到新迷宫数组。同时设计一个全局变量yes，如果到了出口，yes赋值为1 ，探索结束。为了显示所走过的路径，把具体的路线保存在二维数组way中。Way[n][0]代表所走路径的行下标，way[n][1]代表所走路径的列下标，其中的n代表走的步数，根据way数组将走过的路径用红色显示。

3.6 PeopleFind（）人工探索

首先输出迷宫图以及人工控制操作图示。红色探索物出现在左上角，采用人工控制8个方向的移动，由于8个方向，用光标键只能控制4个方向，为了统一，采用了临近的8个字符q、w、e、a、d、z、x、c代表8个方向，按了字符后，对应方向不是墙壁，可以将红色探索无移动到相应位置，按回车键表示人工操作，如果此时map数组元素的坐标是目标出口，则yes赋值为1，表示探索成功，否则赋值为0。

由于探索物在不停地移动，要在新位置显示，并将走过的路恢复为白色通路，可以调用函数DrawPeople（&x,&y,n）完成，参数x和y代表所走过的行坐标和列坐标，n代表

- 10 -

所选的方向，根据n的值将x和y进行相应的变化。

void PeopleFind(int (*map)[N]) {

int x,y;

char c=0;//接收按键的变量 x=y=1;//人工查找的初始位置

setcolor(11);//设置当前画线颜色

line(500,200,550,200);//从当前点开始用增量（x，y）画一直线(int x1,int y1,int x2,int y2)

outtextxy(570,197,\绘制并填充一个扇形(int x,int y,char far*textstring)

3.7 Result（）结果处理函数

因为采用了两种探索方式，但最终结果是找到和没找到两种情况，所以在程序中设计了全局变量yes，根据yes的值进行处理，如果yes为0调用函数NotFind()，显示没找到通路信息，否则调用函数Find()。如果是系统自动探索，Find()会显示出所走过的路径，如果是人工探索，没有记录所走过的路径，只显示找到通路信息。

if(yes)//如果找到 Find(); else//没找到路 NotFind();

3.8 Close()图形关闭函数

调用函数closegraph()关闭图形函数系统，程序结束。

- 11 -

第4章 编码与调试

#include//图形函数 #include//其它函数

#include//此行为文件包含，告诉系统必须包含文件stdio.h，此文件为输入和输出提供支持。

#include//字符屏幕操作函数 #include//接口函数

#define N 20 //迷宫的大小可以改变

int oldmap[N][N];//递归用的数组，用全局变量节约时间 int yes=0;//yes是判断是否找到路的标志，1找到，0没找到

int way[100][2],wayn=0;//way数组是显示路线用的，wayn是统计走了几个格子 void Init(void);//图形初始化 void Close(void);//图形关闭

void DrawPeople(int *x,int *y,int n);//画人工探索物图 void PeopleFind(int (*x)[N]);//人工探索

void WayCopy(int (*x)[N],int(*y)[N]);//为了8个方向的递归，把旧迷宫图拷贝给新数组

int FindWay(int (*x)[N],int i,int j);//自动搜索函数 void MapRand(int (*x)[N]);//随机生成迷宫函数 void PrMap(int (*x)[N]);//输出迷宫图函数 void Result(void);//输出结果处理 void Find(void);//成功处理 void NotFind(void);//失败处理

//主函数

void main(void) {

int map[N][N];//迷宫数组 char ch;

clrscr();//清除正文模式窗口

printf(\选择搜索方式 scanf(\ Init();//图形初始化 MapRand(map);//生成迷宫 PrMap(map);//显示迷宫图 if(ch=='1')

PeopleFind(map);//人工搜索 else

FindWay(map,1,1);//系统自动从下标1,1的地方开始搜索 Result();//输出结果 Close();

- 12 -

}

//图形初始化 void Init(void) {

int gd=DETECT,gm;

initgraph(&gd,&gm,\}

//画人工控制图

void DrawPeople(int *x,int *y,int n) {

//如果将以下两句注释掉，则显示人工走过的路径

setfillstyle(SOLID_FILL,WHITE);//设置白色实体填充样式(int patttern,int color)

bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);//画一个二维条形图(int left,int top,int rigth,int bottom) //恢复原通路

switch(n)//判断x和y的变化，8个方向的变化 {

case 1:(*x)--;break;//上

case 2:(*x)--;(*y)++;break;//右上 case 3:(*y)++;break;//右

case 4:(*x)++;(*y)++;break;//右下 case 5:(*x)++;break;//下

case 6:(*x)++;(*y)--;break;//左下 case 7:(*y)--;break;//左

case 8:(*x)--;(*y)--;break;//左上 }

setfillstyle(SOLID_FILE,RED);//新位置显示探索物

bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6); }

//人工手动查找

void PeopleFind(int (*map)[N]) {

int x,y;

char c=0;//接收按键的变量 x=y=1;//人工查找的初始位置

setcolor(11);//设置当前画线颜色

line(500,200,550,200);//从当前点开始用增量（x，y）画一直线(int x1,int y1,int

- 13 -

x2,int y2)

outtextxy(570,197,\绘制并填充一个扇形(int x,int y,char far*textstring) line(500,200,450,200); outtextxy(430,197,\ line(500,200,500,150); outtextxy(497,130,\ line(500,200,500,250); outtextxy(497,270,\ line(500,200,450,150); outtextxy(445,130,\ line(500,200,550,150); outtextxy(550,130,\ line(500,200,450,250); outtextxy(445,270,\ line(500,200,550,250);

outtextxy(550,270,\以上是画8个方向的控制介绍 setcolor(YELLOW);//设置当前画线颜色(int color)

outtextxy(420,290,\按回车键结束 setfillstyle(SOLID_FILL,R …… 此处隐藏：2556字，全部文档内容请下载后查看。喜欢就下载吧 ……