编程迷宫图
A. 数据结构与算法作业:用c语言编程随机生成一个迷宫,然后找出从入口到出口的路线图。急!
几点说明:
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调试良好
B. c语言数字迷宫问题怎么做图片如下
可以参考八皇后问题用回溯的方式来解决。
这道迷宫题,观察一下,与某个格子相邻的格子至多为4个,也就是有4种可能的前进方向,需要穷举所有可能。在穷举下一种可能前,需要恢复初始状态(即回溯)。写了一个简单的代码,还有很多需要优化的地方,但关键是能用^_^,你可以调试一下,把实现的思路写出来,就可以顺利完成这道题了。
#include <stdio.h>
#include <string.h>
/***
1、 迷宫大小n*n,扩展为(n+2)*(n+2),外围一圈的格子作为不可再前进的边界。
2、 若所有相邻格子均已访问,表明此路不通,回溯。
3、 计数器达到总步数,检查是否位于终点及中间路径是否合法,通过则显示。
4、 查找函数Lookup()以递归方式反复调用自身,a->b->c->...,以查找某条可能的路径。
...c,b,a等返回前,均回溯,逐步恢复tag。
离开a时,tag已经恢复到初始状态,如此就不影响查找其他路径了。
5、 若迷宫够大或数据特别,都可能存在不同的路线
6、 先查看main(),了解基本步骤及初始化过程
***/
const int N = 6;
// eg1. N = 6
int row[N] = { 0, 4, 3, 1, 3, 0}; // 4 + 3 + 1 + 3 = 11
int col[N] = { 0, 1, 4, 3, 3, 0};
// eg2. N = 6
//int row[N] = { 0, 3, 4, 4, 2, 0}; // 3 + 4 + 4 + 2 = 13
//int col[N] = { 0, 3, 2, 4, 4, 0};
// eg3. N = 8
//int row[N] = { 0, 3, 1, 4, 3, 3, 1, 0};
//int col[N] = { 0, 1, 1, 5, 3, 1, 4, 0};
// 计数器
// Lookup()用g_counter与COUNTER比较是否走到了规定的步数
int g_counter = 0; // 无论是否成功,每查找一条路径后自动恢复为0
int COUNTER = 0; // 总步数,等于row(或col)数组各元素之和,在main()中初始化
// Lookup()用tag记录行走状况
// 在main()中初始化
// 每查找一条路径后自动恢复为初始状态
struct _tag
{
int row[N];
int col[N];
int arr[N][N]; // 走过,按顺序标记
} tag;
// 显示迷宫
// inside为false时,打印扩展的迷宫
// inside为true时,打印未扩展的迷宫
void Display(bool inside)
{
int i, j;
for (i = 0; i < N; i++)
{
if ((i == 0 || i == N-1) && inside)
continue;
for (j = 0; j < N; j++)
{
if ((j == 0 || j == N-1) && inside)
printf("%4s", " ");
else
printf("%4d", tag.arr[i][j]);
}
printf(" ");
}
printf(" ");
}
// 检查路径是否符合已给条件
bool Check()
{
bool b = true;
int sum_row, sum_col;
for (int i = 1; i < N-1; i++)
{
sum_row = 0;
sum_col = 0;
for (int j = 1; j < N-1; j++)
{
sum_row += tag.arr[i][j] > 0 ? 1 : 0;
sum_col += tag.arr[j][i] > 0 ? 1 : 0;
}
if (sum_row != row[i] || sum_col != col[i])
{
b = false;
break;
}
}
return b;
}
// 递归查找路径,返回前擦除痕迹,恢复现场
// 当前访问的格子(i,j),i:行坐标,j:列坐标
void Lookup(int i, int j)
{
g_counter++; // 总步数加1
tag.arr[i][j] = g_counter; // visited
tag.row[i]--; // 行计数减1
tag.col[j]--; // 列计数减1
// 走完了
if (g_counter >= COUNTER)
{
// 位于终点,且路径合法
if (i == N-2 && j == N-2 && Check())
{
Display(true);
}
// 此格子已判别,恢复现场,以查找其他路径(此即回溯的思想)
tag.arr[i][j] = 0;
tag.row[i]++;
tag.col[j]++;
g_counter--;
return;
}
// 行方向
if (tag.row[i] > 0)
{
if (!tag.arr[i][j+1])
{
Lookup(i, j+1); // 从当前格子向右走一步
}
if (!tag.arr[i][j-1])
{
Lookup(i, j-1); // 从当前格子向左走一步
}
}
// 列方向
if (tag.col[j] > 0)
{
if (!tag.arr[i+1][j])
{
Lookup(i+1, j); // 从当前格子向下走一步
}
if (!tag.arr[i-1][j])
{
Lookup(i-1, j); // 从当前格子向上走一步
}
}
// 此格子已判别,恢复现场,以查找其他路径(此即回溯的思想)
tag.arr[i][j] = 0;
tag.row[i]++;
tag.col[j]++;
g_counter--;
}
int main()
{
// 格子初始化为全0
memset(tag.arr, 0, sizeof(tag.arr));
for (int i = 0; i < N; i++)
{
tag.row[i] = row[i];
tag.col[i] = col[i];
COUNTER += row[i];
tag.arr[0][i] = 1;
tag.arr[N-1][i] = 1;
tag.arr[i][0] = 1;
tag.arr[i][N-1] = 1;
}
printf("初始化: ");
Display(false);
printf("合法路径: ");
Lookup(1, 1); // 从格子(1, 1)出发
//getchar();
return 0;
}
C. 求编程高手给个JS迷宫的代码。
以下是我作的迷宫:
我作的只有九格的,不过你可以自己改制成任意多格的迷宫.前提是一定要是用我的6个css样式来布局迷宫.否则会出错.核心的javascript我已经测试过了.没有问题
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<title>无标题文档</title>
<style>
.rb{
border-style:double;
border-width:0px;
border-color:#000000;
border-left-width:1px;
border-top-width:1px;
}
.rt{
border-style:double;
border-width:0px;
border-color:#000000;
border-left-width:1px;
border-bottom-width:1px;
}
.lb{
border-style:double;
border-width:0px;
border-color:#000000;
border-right-width:1px;
border-top-width:1px;
}
.lt
{
border-style:double;
border-width:0px;
border-color:#000000;
border-right-width:1px;
border-bottom-width:1px;
}
.lr{
border-style:double;
border-width:0px;
border-color:#000000;
border-top-width:1px;
border-bottom-width:1px;
}
.tb
{
border-style:double;
border-width:0px;
border-color:#000000;
border-left-width:1px;
border-right-width:1px;
}
</style>
</head>
<body>
<div id="layer1" style="position:absolute; left:15px; top:21px; width:27px; height:29px; z-index:1; background-color: #FF0000; layer-background-color: #FF0000; border: 1px none #000000;"></div>
<table width="120" height="120" border="0" cellpadding="0" cellspacing="0" style="border-color:#000000; border-width:1px; border-style:solid; ">
<tr>
<td class="rb"></td>
<td class="rb"></td>
<td class="lb"></td>
</tr>
<tr>
<td class="tb"></td>
<td class="rt"></td>
<td class="lb"></td>
</tr>
<tr>
<td class="rt"></td>
<td class="lr"></td>
<td class="lt"></td>
</tr>
</table>
<script language="javascript">
//得用css来布局迷宫,迷宫的多少行多少列,只要改下面的数据就可以了.不过表格的单元格一定要是40*40
var col=3;//列数
var row=3;//行数
var i=0;//位置数
var player=document.getElementById("layer1");
var td=document.getElementsByTagName("table")[0].getElementsByTagName("td");
document.onkeydown=function (e)
{
e=window.event||e;
if(e.keyCode==37)//向下运动
{
if(i%col!=0)//不在最左边
{
if((td[i].className=="lb"||td[i].className=="lt"||td[i].className=="lr")&&(td[i-1].className=="rb"||td[i-1].className=="rt"||td[i-1].className=="lr"))//可以通过
{
player.style.left=parseInt(player.style.left)-40+"px";
i=i-1;
}
}
}//向左运动
else if(e.keyCode==38)//向上运动
{
if(i>=col)//不在最上边
{
if((td[i].className=="lt"||td[i].className=="rt"||td[i].className=="tb")&&(td[i-col].className=="tb"||td[i-col].className=="rb"||td[i-col].className=="lb"))//可以通过
{
player.style.top=parseInt(player.style.top)-40+"px";
i=i-col;
}
}
}//向上运动
else if(e.keyCode==39)//向右运动
{
if((i%col)!=(col-1))//不在最右边
{
if((td[i].className=="lr"||td[i].className=="rt"||td[i].className=="rb")&&(td[i+1].className=="lb"||td[i+1].className=="lt"||td[i+1].className=="lr"))//可以通过
{
player.style.left=parseInt(player.style.left)+40+"px";
i=i+1;
}
}
}//向右运动
else if(e.keyCode==40)//向下运动
{
if(i<=col*(row-1))//不在最下边
{
if((td[i].className=="lb"||td[i].className=="rb"||td[i].className=="tb")&&(td[i+col].className=="tb"||td[i+col].className=="rt"||td[i+col].className=="lt"))//可以通过
{
player.style.top=parseInt(player.style.top)+40+"px";
i=i+col;
}
}
}//向下运动
}
</script>
</body></html>
D. 走迷宫的C语言版代码求助 程序开始运行时显示一个迷宫地图,迷宫中央有一只老鼠,迷宫的右下方有一个粮
/*注:本程序探索迷宫的优先顺序=> 1-下、2-右、3-上、4-左 <=总体趋势:下右,逆时针方向。因为出口就在右边下方*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define stack_init_size 200
#define stack_increment 10
#define OVERFLOW 0
#define OK 1
#define ERROE 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef struct{
int x;
int y;
}PosType;
typedef struct {
int ord; // 通道块在路径上的"序号"
PosType seat; //通道块在迷宫中的"坐标位置"
int di; //从此通道块走向下一通道块的"方向"
}SElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
int mg[20][20];
/*随机生成迷宫的函数
/*为了能够让尽量能通过,将能通过的块和不能通过的块数量比大致为2:1*/
void Random(){
int i,j,k;
srand(time(NULL));
mg[1][0]=mg[1][1]=mg[18][19]=0; //将入口、出口设置为"0"即可通过
for(j=0;j<20;j++)
mg[0][j]=mg[19][j]=1; /*设置迷宫外围"不可走",保证只有一个出口和入口*/
for(i=2;i<19;i++)
mg[i][0]=mg[i-1][19]=1; /*设置迷宫外围"不可走",保证只有一个出口和入口*/
for(i=1;i<19;i++)
for(j=1;j<19;j++){
k=rand()%3; //随机生成0、1、2三个数
if(k)
mg[i][j]=0;
else{
if((i==1&&j==1)||(i==18&&j==18)) /*因为距入口或出口一步的路是必经之路,故设该通道块为"0"加大迷宫能通行的概率*/
mg[i][j]=0;
else
mg[i][j]=1;
}
}
}
//构造一个空栈
Status InitStack(SqStack &s){
s.base =(SElemType *)malloc(stack_init_size * sizeof(SElemType));
if(!s.base) return OVERFLOW;
s.top=s.base;
s.stacksize=stack_init_size;
return OK;
}
//当前块可否通过
Status Pass(PosType e){
if (mg[e.x][e.y]==0) //0时可以通过
return OK; // 如果当前位置是可以通过,返回1
return OVERFLOW; // 其它情况返回0
}
//留下通过的足迹
Status FootPrint(PosType e){
mg[e.x][e.y]=7;
return OK;
}
//压入栈
Status Push(SqStack &s,SElemType e){
if(s.top-s.base>=s.stacksize){
s.base=(SElemType *)realloc(s.base,(s.stacksize+stack_increment) *sizeof(SElemType));
if(!s.base)exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=stack_increment;
}
*s.top++=e;
return OK;
}
//出栈
Status Pop(SqStack &s,SElemType &e){
if(s.top==s.base)
return ERROE;
e=*--s.top;
return OK;
}
//下一步
PosType NextPos(PosType &e,int dir){
PosType E;
switch(dir){
case 1:E.x=e.x; //向下
E.y=e.y+1;
break;
case 2:E.x=e.x+1; //向右
E.y=e.y;
break;
case 3:E.x=e.x; //向上
E.y=e.y-1;
break;
case 4:E.x=e.x-1; //向左
E.y=e.y;
break;
}
return E;
}
//是否空栈
Status StackEmpty(SqStack s){
if (s.top==s.base)
return OK;
return OVERFLOW;
}
//留下不能通过的足迹
Status MarkPrint(PosType e){
mg[e.x][e.y]=3;
return OK;
}
//迷宫函数
// 若迷宫maze中从入口 start到出口 end的通道,则求得一条存放在栈中
// (从栈底到栈顶),并返回TRUE;否则返回FALSE
Status MazePath(int mg,PosType start,PosType end,SqStack &s){
PosType curpos;
InitStack(s);
SElemType e;
int curstep;
curpos=start; // 设定"当前位置"为"入口位置"
curstep=1; // 探索第一步
do{
if(Pass(curpos)){ // 当前位置可通过,即是未曾走到过的通道块
FootPrint(curpos); // 留下足迹
e.di =1;
e.ord = curstep;
e.seat= curpos;
Push(s,e); // 加入路径
if(curpos.x==end.x&&curpos.y==end.y){
printf("\n\n0∩_∩0 能到达终点!");
return TRUE;
}
curpos=NextPos(curpos,1); // 下一位置是当前位置的东邻
curstep++; // 探索下一步
}
else{ // 当前位置不能通过
if(!StackEmpty(s)){
Pop(s,e);
while(e.di==4&&!StackEmpty(s)){
MarkPrint(e.seat);
Pop(s,e);
}
if(e.di<4){
e.di++;
Push(s,e); // 留下不能通过的标记,并退回一步
curpos=NextPos(e.seat,e.di); /* 当前位置设为新方向的相邻块*/
}//if
}//if
}//else
}while(!StackEmpty(s));
printf("\n\n囧 ! 不能到达终点!");
return FALSE;
}
//打印迷宫
void PrintMaze(){
int i,j;
printf("运行路径:\n\n");
for(i=0;i<20;i++){
for(j=0;j<20;j++){
if(mg[i][j]==0)printf(" ");
else if(mg[i][j]==1) printf("■"); //迷宫的"墙"
else if(mg[i][j]==3) printf("◇"); //不通的路
else if(mg[i][j]==7)printf("○"); //通过的路径
}
printf("\n");
}
printf("\n");
}
void main(){
SqStack S;
PosType start,end;
start.x=1;start.y=0; //起点坐标
end.x=18;end.y=19; //终点坐标
printf("\n==================迷宫游戏==================");
printf("\n说明:■不能走的区域\t◇走不通的区域");
printf("\n '空格'代表未到过的区域");
printf("\n ○代表能通过的路径,指向终点");
printf("\n============================================");
Random();
printf("\n\nTest 1:");
MazePath(mg[20][20],start,end,S);
PrintMaze();
system("pause");
Random();
printf("\nTest 2:");
MazePath(mg[20][20],start,end,S);
PrintMaze();
system("pause");
Random();
printf("\nTest 3:");
MazePath(mg[20][20],start,end,S);
PrintMaze();
printf("\n==========程序退出,感谢使用!==========\n");
}