Question

数据结构与算法作业：用C语言编程随机生成一个迷宫，然后找出从入口到出口的路线图。急！

必须是原创！！！谢谢！！我的邮箱：wwfhit@126.com.在邮件里附上昵称我好给加分。
编译器是codeblocks，或者VC！！

Answer 1

几点说明：
1．本程序是动态的，运行后自动寻找迷宫出路
2.本程序对C语言刚学完的有很大的意义．
3.四周是墙,坐标(1,1)是入口,右下脚是出口
声明:本程序用VC调试是无法通过的需要修改
本程序调试工具是TC.....................
#include "graphics.h"
#include "dos.h"
#include "stdlib.h"
#include "process.h"

#define MAX_COL 14/*定义迷宫大小*/
#define MAX_ROW 14

typedef struct
{ int vert;
int horiz;
}offsets;

mapture(int i,int j,int k);/*标记迷宫，（i,j）标记为k模式*/
initmaze();/*初始化迷宫数组*/
findmaze(int i,int j);/*找到了（i,j）可走，标记*/
mapmaze();/*画出原始迷宫*/
int findpath(int row,int col);/*递归函数，找出迷宫路径*/
mapbar();/*画出方格*/
initgrap();/*初始化VGA*/
print();/*迷宫走完后，输出是否成功 */

int startx=50,starty=50;/*画图的屏幕坐标*/
int maze[MAX_ROW][MAX_COL];
offsets move[8]={{0,1},{1,1},{-1,1},{1,0},{-1,0},{0,-1},{1,-1},{-1,-1}}; /*8个方向寻找*/

initmaze()/*初始化迷宫数组 */
{ int i,j;

for(i=0;i<MAX_ROW;i++)/*迷宫四周设置为1 代表墙*/
{ maze[i][0]=1;
maze[i][MAX_COL-1]=1;
}
for(i=0;i<MAX_COL;i++)
{ maze[0][i]=1;
maze[MAX_ROW-1][i]=1;
}
randomize();
for(i=1;i<MAX_ROW-1;i++)/*迷宫图形随机产生 1表示不通 0表示可行*/
for(j=1;j<MAX_COL-1;j++)
{
maze[i][j]=random(2);
}

}

findmaze(int i,int j)/*找到 （i,j）可走*/
{
mapture(j,i,2);/*在图形上标记*/
sleep(1);

}

returnmaze(int i,int j)/*找到（i,j）可走 ，但下一步无路走则标记*/
{

mapture(j,i,3);/*在图形上标记*/
sleep(1);
}

print(int i)/*迷宫走完后，输出是否成功*/
{ settextstyle(1,0,5);
if(i==1)
outtextxy(340,400,"Ture path!");
else if(i==2)
outtextxy(340,400,"No path!");

}

int findpath(int row,int col)/*用递归法找迷宫*/
{ int direct,next_row,next_col;
direct=0;
maze[1][1]=2;
mapture(1,1,2);
sleep(1);
while(direct<8)/*8个方向寻找*/
{ next_row=row+move[direct].vert;/*设置下一步坐标*/
next_col=col+move[direct].horiz;
if(maze[next_row][next_col]==0) /*可走，便标记*/
{ maze[next_row][next_col]=2;
findmaze(next_row,next_col) ;
if(next_row==(MAX_ROW-2)&&next_col==(MAX_COL-2))/*找到出口退出程序*/
{ print(1);
getch();
exit(0);
}
else
findpath(next_row,next_col);/*没有到出口继续递归*/
maze[next_row][next_col]=3;
returnmaze(next_row,next_col);
}
direct++;
}
return(row);
}

TC调试良好

Answer 2

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>

/* define the size of maze */
#define MAX_COL 6
#define MAX_ROW 6
#define TRUE 1
#define FALSE 0
#define IS_USABLE(a, b) (a >= 0 && a < MAX_ROW) && (b >= 0 && b < MAX_COL) && maze[a][b] && (!my_maze[a][b])
static int maze[MAX_ROW][MAX_COL];
static int target_maze[MAX_ROW][MAX_COL];

static void init_maze();
static int move_to(int i, int j, int (*maze)[MAX_COL], int count);
static void print_maze(int (*maze)[MAX_COL]);

static void init_maze()
{
int i, j;

srand((unsigned) time(NULL));

for (i = 0; i < MAX_ROW; i++)
for(j = 0; j < MAX_COL; j++) {
maze[i][j] = (int) (rand() % 2);
}
maze[1][0] = 1; /* start point */
maze[MAX_ROW - 1][MAX_COL - 2] = 1; /* end point */
}

static int move_to(int _i,int _j, int (*in_maze)[MAX_COL], int count) {
int my_maze[MAX_ROW][MAX_COL], i, j;

if (!in_maze) {
for (i = 0; i < MAX_ROW; i++)
for(j = 0; j < MAX_COL; j++) {
my_maze[i][j] = 0;
}
} else {
for (i = 0; i < MAX_ROW; i++)
for(j = 0; j < MAX_COL; j++) {
my_maze[i][j] = in_maze[i][j];
}
}

my_maze[_i][_j] = count;
/* reach the end point */
if (_i == MAX_ROW - 1 && _j == MAX_COL - 2) {
for (i = 0; i < MAX_ROW; i++)
for(j = 0; j < MAX_COL; j++) {
target_maze[i][j] = my_maze[i][j];
}
return TRUE;
}

if (IS_USABLE(_i - 1, _j)) {
if (move_to(_i - 1, _j, my_maze, count + 1))
return TRUE;
}
if (IS_USABLE(_i + 1, _j)) {
if (move_to(_i + 1, _j, my_maze, count + 1))
return TRUE;
}
if (IS_USABLE(_i, _j - 1)) {
if (move_to(_i, _j - 1, my_maze, count + 1))
return TRUE;
}
if (IS_USABLE(_i, _j + 1)) {
if (move_to(_i, _j + 1, my_maze, count + 1))
return TRUE;
}
return FALSE;
}

static void print_maze(int (*maze)[MAX_COL]) {
int i, j;

for (i = 0; i < MAX_ROW; i++) {
for(j = 0; j < MAX_COL; j++) {
if (maze[i][j] != 0)
printf("%d ", maze[i][j]);
else
printf(" ");
}
printf("\n");
}
}

int main()
{
while(1) {
init_maze();
printf("Out put the maze :\n");
print_maze(maze);
if (move_to(1, 0, NULL, 1)) {
printf("Out put the path :\n");
print_maze(target_maze);
break;
} else {
printf("No way!\n");
}
}
}
VC60下正常运行