⑴ 急！急！急！如何用c语言编写一个走迷宫的游戏
#include<stdio.h>樱弯
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<graphics.h>扒睁
#define x1 (a-120)/脊此闷20
#define y1 (b-40)/20
#define UP 72
#define DOWN 80
#define LEFT 75
#define RIGHT 77
#define ENTER 13
#define ESC 27
int d[21][21]={0};
int a=120,b=40;
void init()
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"d:\\tc20");
}
void drawlist()
{
int i,j;
setbkcolor(BLACK);
setcolor(RED);
for(i=0,j=0;i<=20,j<=20;i++,j++)
{
line(i*20+120,40,i*20+120,440);
line(120,40+20*j,520,40+20*j);
}
}
void drawfirst()
{
gotoxy(120,40);
setcolor(YELLOW);
circle(120+10,40+10,6);
setfillstyle(1,BROWN);
floodfill(120+10,40+10,YELLOW);
}
void clearold(int m,int n)
{
setfillstyle(1,BLACK);
floodfill(m+10,n+10,YELLOW);
setcolor(BLACK);
circle(m+10,n+10,6);
}
void drawnew(int m,int n)
{
setcolor(YELLOW);
circle(m+10,n+10,6);
setfillstyle(1,BROWN);
floodfill(m+10,n+10,YELLOW);
}
void filllist()
{
int i,j,t,m;
randomize();
for(i=0;i<=18;i++)
for(j=1;j<=19;j++)
{ t=random(2)
if(t==1)
{
setfillstyle(1,1);
floodfill(121+20*i,41+20*j,RED);
d[i][j]=1;}
else d[i][j]=0;
}
d[0][0]=0;d[19][19]=0;
setfillstyle(1,BLACK);
floodfill(121,41,RED);
floodfill(121+19*20,41+19*20,RED);
}
void getway()
{
int flag=1;
while(flag==1)
{
gotoxy(a,b);
for(;b<=440&&a<=520&&a>=120&&b>=40;)
{
switch(getch())
{
case UP : {
if(b==40);
else if(d[(b-40)/20-1][(a-120)/20]==0)
{clearold(a,b);gotoxy(a,b=b-20);drawnew(a,b);}
else;
break;}
case DOWN:{
if(b==440);
else
if(d[(b-40)/20+1][(a-120)/20]==0){clearold(a,b);gotoxy(a,b=b+20);drawnew(a,b);}else;
break; }
case RIGHT : {
if(b==520);
else
if(d[(b-40)/20][(a-120)/20+1]==0){clearold(a,b);gotoxy(a=a+20,b);drawnew(a,b);}else;
break; }
case LEFT : {
if(b==120);
else
if(d[(b-40)/20][(a-120)/20-1]==0){clearold(a,b);gotoxy(a=a-20,b);drawnew(a,b);}else;
break;}
case ESC : exit();break;
default : break;
if(a==500&&b==420)break;
}/*switch finish*/
}/*for finish*/
}/*while finish*/
}
void main()
{
init();
drawlist();
filllist();
drawfirst();
getway();
getch();
closegraph();
}
⑵ 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语言编写一个迷宫程序
#include
⑷ 12345迷宫的三种解法
递归求解、回溯求解和队列求解。迷宫求解是c语言编程芦裂中的数学题，有三种解题方法分别是递归求解、回溯求解和队列求解，其中在回溯解法中，主要是用栈纤燃来存储可以探索的位置，利用栈后进先出的特点，在一条分路上探索失败时，回到最近一次存储的可探索位置，这是一种深度毁哗虚优先搜索的方法。
⑸ 如何用C语言编写一个迷宫程序
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定义迷宫内点的坐标类型
{
int x;
int y;
};
struct Element //"恋"栈元素，嘿嘿。。
{
int x,y; //x行,y列
int d; //d下一步的方向
};
typedef struct LStack //链栈
{
Element elem;
struct LStack *next;
}*PLStack;
/*************栈函数****************/
int InitStack(PLStack &S)//构造空栈
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判断栈是否为空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//压入新数据元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //栈顶元素出栈
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宫路径函数***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //开始为-1
Push(S1,elem);
while(!StackEmpty(S1)) //栈不为空 有路径可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一个方向
while(d<4) //试探东南西北各个方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴
}
if(maze[a][b]==0) //找到可以前进的非出口的点
{
maze[a][b]=2; //标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //当前位置入栈
i=a; //下一点转化为当前点
j=b;
d=-1;
}
d++;
}
}
printf("没有找到可以走出此迷宫的路径\n");
}
/*************建立迷宫*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宫行,列 [/M]
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为(最外圈为强)...\n");
for(i=0;i<=m+1;i++) //加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北 [/M]
initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}
⑹ 用C语言编写一个迷宫程序，知道出处也行 ~~！
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定义迷宫内点的坐标类型
{
int x;
int y;
};
struct Element //"恋"栈元素，嘿嘿。。
{
int x,y; //x行迅枯核,y列
int d; //d下一步的方向
};
typedef struct LStack //链栈
{
Element elem;
struct LStack *next;
}*PLStack;
/*************栈函数****************/
int InitStack(PLStack &S)//构造空栈
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判断栈是否为空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//压入新数据元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //栈顶元素出栈
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宫路径函数***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口点作上标记
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //开始为-1
Push(S1,elem);
while(!StackEmpty(S1)) //栈不为空 有路径可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一败陪个方向
while(d<4) //试探东南西北各个方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");
while(S1) //逆置序列 并输出迷宫路径序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴
}
if(maze[a][b]==0) //找到可以前进的非出口的点
{
maze[a][b]=2; //标记走过此点
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //当前位置亩掘入栈
i=a; //下一点转化为当前点
j=b;
d=-1;
}
d++;
}
}
printf("没有找到可以走出此迷宫的路径\n");
}
/*************建立迷宫*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宫行,列 [/M]
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宫为(最外圈为强)...\n");
for(i=0;i<=m+1;i++) //加一圈围墙
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //输出迷宫
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐标
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北 [/M]
initmaze(sto);//建立迷宫
printf("输入入口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&start.x,&start.y);
printf("输入出口的横坐标,纵坐标[逗号隔开]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}
⑺ 回溯法的用回溯法解题的一般步骤
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解贺腔空间，并在搜索过程中用剪枝函数避免无效搜索。
回溯法C语言举例
八皇后问题是能用回溯法解决的一个经典问题。
八皇后问题是一个古老而着名的问题。该问销差题是十九世纪着名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上禅斗衫的状态 ：
a[] a[i]=0表示第i行上还没有皇后；
b[] b[i]=0表示第i列反斜线/上没有皇后；
c[] c[i]=0表示第i列正斜线上没有皇后。
棋盘中同一反斜线/上的方格的行号与列号之和相同；同一正斜线上的方格的行号与列号之差均相同，这就是判断斜线的依据。
初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m列，col[m]行的位置设定有皇后的标志；当从第m列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。 #include<stdio.h>
#include<stdlib.h>
#define Queens 8
int a[Queens+1]; //八皇后问题的皇后所在每一行位置，从1开始算
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1;//初始
a[1]=1;
printf(the possible configuration of 8 queesns are:
);
while(not_finish) //not_finsh=1:处理未结束
{
while(not_finish && i<Queens+1) //处理未结束
{
for(flag=1,k=1;flag && k<i;k++)//判断是否有多个皇后在同一行
if(a[k]==a[i])
flag=0;
for(k=1;flag && k<i;k++) //判断是否有多个皇后在对角线
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))
flag=0;
if(!flag) //若存在矛盾 重设第i个元素
{
if(a[i]==a[i-1]) //若a[i]的值已经已经一圈追上a[i-1]的值
{
i--; //退回一步 重新试探处理前一个元素
if(i>1 && a[i]==Queens)
a[i]=1; // 当a[i]为 Queens时 将a[i]的值重置
else
if(i==1 && a[i]==Queens)//当第一未位的值达到Queens时结束
not_finish=0;
else
a[i]++;
}
else
if(a[i]==Queens)
a[i]=1;
else
a[i]++;
}
else
if(++i<=Queens) //若前一个元素的值为Queens
if(a[i-1]==Queens)
a[i]=1;
else //否则元素为前一个元素的下一个值
a[i]=a[i-1]+1;
}
if (not_finish)
{
++count;
printf((count-1)%3?[%2d]::
[%2d]:,count);
for(k=1;k<=Queens;k++) //输出结果
printf(%d,a[k]);
if(a[Queens-1]<Queens)
a[Queens-1]++;
else
a[Queens-1]=1;
i=Queens-1;
}
}
system(pause);
} var
n,k,t,i:longint;
x:array[1..100] of integer;
function pa(k:integer):boolean;
begin
pa:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then pa:=false;
end;
procere try(k:integer);
var
i:integer;
begin
if k>n then
begin
t:=t+1;
exit;
end;
for i:=1 to n do
begin
x[k]:=i;
if pa(k) then try(k+1);
end;
end;
begin
read(n);
t:=0;
try(1);
write(t);
end. #include
#include
#define m 5
#define n 6
int sf=0;
int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}};
void search(int x,int y)
{
if((x==m-1)&&(y==n-1))
sf=1;
else
{
mase[x][y]=1;
if((sf!=1)&&(y!=n-1)&&mase[x][y+1]==0)
search(x,y+1);
if((sf!=1)&&(x!=m-1)&&mase[x+1][y]==0)
search(x+1,y);
if((sf!=1)&&(y!=0)&&mase[x][y-1]==0)
search(x,y-1);
if((sf!=1)&&(x!=0)&&mase[x-1][y]==0)
search(x-1,y);
}
mase[x][y]=0;
if(sf==1)
mase[x][y]=5;//通过路径用数字的表示
}
int main()
{
int i=0,j=0;
//clrscr();
search(0,0);
for(i=0;i<m;i++) p=></m;i++)>
{
for(j=0;j<n;j++) p=></n;j++)>
printf(%d,mase[i][j]);
printf(
);
}
system(pause);
return 0;
}
回溯法解决迷宫问题PASCAL语言
program migong;
var
n,k,j,x,y:integer;
a:array[0..10000,0..10000] of integer;
b:array[0..1000000,0..2] of integer;
procere search(x,y,i:integer);
begin
a[x,y]:=1;
if (x=n) and (y=n) then
begin
for j:=1 to i-1 do
writeln(j,':(',b[j,1],',',b[j,2],')');
writeln(i,':(',x,',',y,')');
halt;
end;
if a[x-1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x-1,y,i+1);end;
if a[x+1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x+1,y,i+1);end;
if a[x,y-1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y-1,i+1);end;
if a[x,y+1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y+1,i+1);end;
a[x,y]:=0;
end;
begin
read(n);
for k:=1 to n do
for j:=1 to n do
read(a[k,j]);
for k:=0 to n+1 do
begin
a[k,0]:=-1;
a[k,n+1]:=-1;
a[n+1,k]:=-1;
a[0,k]:=-1;
end;
x:=1;y:=1;
if a[x+1,y]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x+1,y,1);a[x,y]:=0;end;
if a[x,y+1]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x,y+1,1);a[x,y]:=0;end;
end.
⑻ C语言编程求解啊！利用回溯算法的迷宫搜索类型问题
#include "stdafx.h"
#include <iostream>
#include "cmath"
#include <fstream>
using namespace std ;
int ROW ;
int COL ;
int **g_pRoom ;
// 回溯法注意标记已访问过的节点。。。。。不然就会进入重复操作将栈用空。。。。。。。。
struct Point
{
Point( int xx = 0, int yy = 0 ):x(xx),y(yy) { }
int x ;
int y ;
} ;
int g_nMax = 0 ;
Point g_pResult[100] ;
int g_nCount ;
Point g_pStart ;
Point g_pEnd ;
Point g_pOrient[4] = { Point(-1, 0 ) , Point( 0 ,1 ) , Point( 1 ,0 ) , Point( 0 , -1 ) } ;
bool Read_data( ifstream &file )
{
if( file.eof() )
return false ;
g_nMax = 0 ;
g_nCount = 0 ;
file>>ROW>>COL ;
g_pRoom = new int*[ROW] ;
g_pStart = g_pEnd = Point( -1, -1 ) ;
for( int i = 0 ; i < ROW ; i++ )
g_pRoom[i] = new int[COL] ;
for( int i = 0 ; i < ROW ; i++ )
for( int j = 0 ; j < COL ; j++ )
{
file>>g_pRoom[i][j] ;
if( g_pRoom[i][j] == -1 )
{
g_pStart.x = j ;
g_pStart.y = i ;
}
else if( g_pRoom[i][j] == -2 )
{
g_pEnd.x = j ;
g_pEnd.y = i ;
}
}
if( g_pStart.x == -1 || g_pEnd.x == -1 )
{
cout<<" the data errror !\n" ;
return false ;
}
return true ;
}
void Dateback( Point pStart )
{
static Point Stack[1000] ;
static int nTop = 0 ;
static int Apple = 0 ;
if( pStart.x == g_pEnd.x && pStart.y == g_pEnd.y )
{
if( Apple + 2 > g_nMax )
{
g_nMax = Apple + 2 ;
for( int i = 0 ; i < nTop ; i++ )
g_pResult[i] = Stack[i] ;
g_nCount = nTop ;
} // ....
}
else
{
for( int i = 0 ; i < 4 ; i++ )
{
Point s ;
s.x = pStart.x + g_pOrient[i].x ;
s.y = pStart.y + g_pOrient[i].y ;
if( s.x >= 0 && s.x < COL && s.y >= 0 && s.y < ROW && g_pRoom[s.y][s.x] != 0 )
{
Apple += g_pRoom[s.y][s.x] ;
Stack[nTop++] = s ;
int temp = g_pRoom[s.y][s.x] ;
g_pRoom[s.y][s.x] = 0;
Dateback( s ) ;
nTop-- ;
g_pRoom[s.y][s.x] = temp ;
Apple -= g_pRoom[s.y][s.x] ;
}
}
}
}
int main()
{
ifstream file("data.txt") ;
Read_data(file) ;
Dateback( g_pStart ) ;
cout<<g_nMax ;
cout<<"("<<g_pStart.y<<","<<g_pStart.x<<")"<<" " ;
for( int i = 0 ; i < g_nCount ; i++ )
cout<<"("<<g_pResult[i].y<<","<<g_pResult[i].x<<")"<<" " ;
return 0 ;
}
⑼ 数据结构迷宫问题（c语言）
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
int m,n,num,map[101][101],f[101][101],a[101],b[101],d[2][4]={0,-1,0,1,-1,0,1,0},ans,flag;
void maze()
{
int i,j;
time_t t;
srand(time(&t));
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
map[i][j]=rand()%2;
if(map[i][j])
num++;
}
if(num<m*n/2)
{
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(!map[i][j])
map[i][j]+=rand()%2;
}
map[0][0]=1;
map[m-1][n-1]=1;
}
void print()
{
int i,j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
printf("%d ",map[i][j]);
if(j==n-1)puts("");
}
}
void dfs(int x,int y)
{
int i,tx,ty;
if(!flag)
return;
for(i=0;i<4;i++)
{
tx=x+d[0][i];
ty=y+d[1][i];
if(!f[tx][ty]&&tx>=0&&ty>=0&&tx<m&&ty<n&&map[tx][ty])
{
f[tx][ty]=1;
a[ans]=tx;
b[ans++]=ty;
if(tx+ty==0)
{
printf("(%d,%d)\n",m,n);
for(flag=i=0;i<ans;i++)
printf("(%d,%d)\n",a[i]+1,b[i]+1);
return;
}
dfs(tx,ty);
f[tx][ty]=0;
ans--;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n),m+n)
{
memset(f,0,sizeof(f));
num=ans=0;
flag=1;
maze();
print();
dfs(m-1,n-1);
if(flag)
puts("There is no path");
}
return 0;
}
⑽ C语言 栈 迷宫 的一个疑问
全部程序分几个文件，看清楚了，每段程序放入一个文件，每段程序前面都有文件名： //stackoperation.cpp Status InitStack(SqStack &S) { //构造一个空栈S S.base = (SElemType *)malloc(RANGE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top = S.base; S.stacksize = RANGE; return OK; }//Initstack Status Push(SqStack &S,SElemType e) { //插入元素e为新的栈顶元素 if(S.top - S.base >= S.stacksize){//栈满，追加存储空间 S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; }//Push Status Pop(SqStack &S,SElemType &e){ /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK； 否则返回迅液ERROR*/ if(S.top == S.base) return ERROR; e = * --S.top; return OK; }//Pop bool StackEmpty(SqStack S) { //判断栈是否为空并返回TURN或FALSE if(S.top == S.base) return TURE; return FALSE; }//StackEmpty void PrintStack() { SqStack ST; SElemType e; InitStack(ST); do{ Pop(SqS,e); Push(ST,e); }while(!StackEmpty(SqS)); do{ Pop(ST,e); printf("(%d,%d,%d)",e.seat.i,e.seat.j,e.di); }while(!StackEmpty(ST)); } //migong.cpp #include "Basetype.h" #include "stackoperation.cpp" #include "Mazeoperation.cpp" void main() { char filename[15]; FILE *fp; printf("请输入迷宫数据文件名（长度不超过15个字符）："); scanf("%s",&filename); //如档茄找不到文件，则要求重新输入（最多三次机会） for(int i=0;i<3;i++){ if((fp = fopen(filename,"r")) == NULL) {printf("不能打开文件,请重新输入文件名（长度不超过15个字符）：\n"); scanf("%s",filename); }//if break; }//for //读取迷宫的行数和列数 int rnum,cnum; fscanf(fp,"%d,%d",&rnum,&cnum); printf("这个迷宫有%d行，%d列\n",rnum,cnum); if(rnum>RANGE-2 || cnum>RANGE-2) { printf("迷宫太大，无法求解\n"); return; }//判断迷宫的大小是否符合要求 //初始化一个迷宫变量 MazeType maze; for(i=0;i<=rnum+1;i++) for(int j=0;j<=cnum+1;j++) maze.arr[i][j] = '#'; CreatMaze(maze,rnum,cnum,fp);//创建迷宫 fclose(fp);//关闭迷宫文件 //打印当前迷宫 printf("当前迷宫为：\n"); for(i=0;i<=rnum+1;i++) { for(int j=0;j<=cnum+1;j++) printf("%c",maze.arr[i][j]); printf("\n"); } printf("其亩蠢物中'#'表示障碍,外围一圈'#'为围墙\n"); //读取入口及出口位置 PosType startp,endp; printf("请输入入口位置（两数中间以逗号相隔）："); scanf("%d,%d",&startp.i,&startp.j); printf("请输入出口位置（两数中间以逗号相隔）："); scanf("%d,%d",&endp.i,&endp.j); if(MazePath(maze,startp,endp)) { PrintMaze(maze,rnum,cnum);//将求解的迷宫输出到文件保存，并打印到屏幕 PrintStack();//如果存在路径则打印之 } else printf("此迷宫不存在路径\n"); }//main //Mazeoperation.cpp bool Pass(MazeType maze,PosType curpos) { //判断当前位置是否可通，并返回值 switch(char ch = maze.arr[curpos.i][curpos.j]) { case' ': return(FALSE); case'#': case'@': case'*': return(TURE); default: { printf("迷宫中第%d行,第%d列出现不明字符%c\n", curpos.i,curpos.j,ch);exit(0);} }//switch }//pass void FootPrint(MazeType &maze,PosType curpos) { maze.arr[curpos.i][curpos.j] = '*'; }//FootPrint void MarkPrint(MazeType &maze,PosType curpos) { maze.arr[curpos.i][curpos.j] = '@'; }//MarkPrint void NextPos(PosType &curpos,int di) { switch(di) { case 1: curpos.j++;break; case 2: curpos.i++;break; case 3: curpos.j--;break; case 4: curpos.i--;break; default: printf("当前方向%d无效\n",di); exit(0); }//switch }//NextPos bool MazePath(MazeType &maze,PosType start,PosType end){ SElemType e; InitStack(SqS); PosType curpos = start; int curstep = 1; do{ if(!Pass(maze,curpos)){ FootPrint(maze,curpos); e.order = curstep; e.seat.i = curpos.i;e.seat.j = curpos.j; e.di = 1; Push(SqS,e); if(curpos.i == end.i && curpos.j == end.j) return(TURE); NextPos(curpos,1); curstep++; }//if else{ if(!StackEmpty(SqS)){ Pop(SqS,e); while(e.di == 4 && !StackEmpty(SqS)){ MarkPrint(maze,e.seat); Pop(SqS,e); }//while if(e.di<4){ e.di++; Push(SqS,e); NextPos(e.seat,e.di); curpos.i = e.seat.i;curpos.j = e.seat.j; }//if }//if }//else }while(!StackEmpty(SqS)); return(FALSE); }//Mazepath void CreatMaze(MazeType &maze,int row,int col,FILE *fp){ //建立迷宫 char ch = fgetc(fp); for(int i=1;i<=row;i++) { for(int j=1;j<=col;j++) {switch( ch = fgetc(fp)) { case'0': maze.arr[i][j]=' ';break; case'1': maze.arr[i][j]='#';break; default: printf("迷宫第%d行第%d列数据为%c有错误",i,j,ch);exit(0); }//switch }//for fseek(fp,2,1); }//for fclose(fp); }//CreatMaze void PrintMaze(MazeType maze,int row,int col) { //打印结果并输出到文件保存 FILE *out; if((out = fopen("outfile","w"))==NULL) { printf("不能打开文件\n"); exit(0); }//if for(int i=0;i<=row+1;i++) {for(int j=0;j<=col+1;j++) { fputc(maze.arr[i][j],out); printf("%c",maze.arr[i][j]); } printf("\n"); } printf("其中'*'号代表路径，'#'代表障碍,'@'代表死胡同\n"); fclose(out);//关闭文件 } //Basetype.h #include <stdio.h> #include "stdlib.h" #define RANGE 30 //栈的存储空间初始分配量， //以及用来存放迷宫的字符数组的最大维数 #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define STACKINCREMENT 5 //栈的存储空间分配增量 typedef struct{ int i; //行坐标 int j; //列坐标 }PosType; //迷宫中坐标位置类型 //栈的定义 typedef struct{ int order; //通道块在路径上的“方向” PosType seat; //通道块在迷宫中的“坐标位置” int di; //从此通道块走向下一通道块的“方向” }SElemType; //栈的元素类型 typedef struct{ SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单位 }SqStack; //迷宫的定义 typedef struct{ int m,n; char arr[RANGE][RANGE]; }MazeType; typedef int Status; SqStack SqS; //定义一个栈 ~