当前位置:首页 » 编程语言 » 迷宫问题路径c语言
扩展阅读
webinf下怎么引入js 2023-08-31 21:54:13
堡垒机怎么打开web 2023-08-31 21:54:11

迷宫问题路径c语言

发布时间: 2023-05-24 11:44:56

A. 数据结构迷宫问题(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;
}

B. 如何用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. 数据结构C语言版的迷宫问题如何解决

#include"iostream.h"
#include"stdlib.h"
#include"stdio.h"
#define M 10
#define N 10
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=4; //方向输出为-1 判断是否到了出口
Push(S1,elem);
printf("0=东 1=南 2=西 3=北 4为则走出迷宫\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);
}
printf("成功 !\n");
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; //迷宫行,列
printf("请输入迷宫的行数 m=");
scanf("%d",&m);
printf("请输入迷宫的列数 n=");
scanf("%d",&n);
printf("请输入迷宫的各行各列:(用空格隔开,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}};//行增量和列增量 方向依次为东西南北
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); //寻找路径
}

D. c语言的迷宫问题

//寻路_带权重_带障碍_最短_文件地图_不闪------wlfryq------//
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>

typedefstruct
{
intx;
inty;
}_PT;

_PTpt;
introw=0,col=0;

//设置CMD窗口光标位置
voidsetxy(intx,inty)
{
COORDcoord={x,y};
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
}
//获取当前CMD当前光标所在位置
voidgetxy()
{
HANDLEhConsole=GetStdHandle(STD_OUTPUT_HANDLE);
COORDcoordScreen={0,0};//光标位置
CONSOLE_SCREEN_BUFFER_INFOcsbi;
if(GetConsoleScreenBufferInfo(hConsole,&csbi))
{
pt.x=csbi.dwCursorPosition.X;
pt.y=csbi.dwCursorPosition.Y;
}
}

typedefstruct
{
intx;
inty;
inttype;
intv;
}PT;

PT**s=NULL,stack[50],start,end,c;
intpos=0;

voidprt()
{
inti,j;
system("cls");
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(s[i][j].type==1)
{
printf("■");
}
elseif(i==end.x&&j==end.y)
{
printf("★");
}
elseif(i==c.x&&j==c.y)
{
printf("◎");
}
else
{
printf("");
}
}
printf(" ");
}
Sleep(500);
}

voidstack_in(PTa)
{
stack[pos++]=a;
}

PTstack_out()
{
inti;
PTt;
t=stack[0];
for(i=0;i<pos-1;i++)
{
stack[i]=stack[i+1];
}
pos--;
returnt;
}

voidfun()
{
PTa;
intx,y,v;
while(1)
{
if(pos==0)
{
break;
}
a=stack_out();
x=a.x;
y=a.y;
if(x==start.x&&y==start.y)
{
break;
}
v=s[x][y].v;
if(x-1>=0&&s[x-1][y].type==0&&(s[x-1][y].v==-1||s[x-1][y].v>v+1))
{
s[x-1][y].v=v+1;
stack_in(s[x-1][y]);
}
if(x+1<=row-1&&s[x+1][y].type==0&&(s[x+1][y].v==-1||s[x-1][y].v>v+1))
{
s[x+1][y].v=v+1;
stack_in(s[x+1][y]);
}
if(y-1>=0&&s[x][y-1].type==0&&(s[x][y-1].v==-1||s[x-1][y].v>v+1))
{
s[x][y-1].v=v+1;
stack_in(s[x][y-1]);
}
if(y+1<=col-1&&s[x][y+1].type==0&&(s[x][y+1].v==-1||s[x-1][y].v>v+1))
{
s[x][y+1].v=v+1;
stack_in(s[x][y+1]);
}
}
}

voidgo(intx,inty)
{
printf(" 按任意键开始 ");
getchar();
intv;
while(1)
{
if(x==end.x&&y==end.y)
{
setxy(0,y+2);
printf("end....");
return;
}
v=s[x][y].v;
if(v==0)
{
return;
}
if(x-1>=0&&s[x-1][y].v==v-1)
{
c=s[x-1][y];
setxy(y*2,x);
x=x-1;
printf("");
setxy(y*2,x);
printf("◎");
Sleep(500);
continue;
}
elseif(x+1<=row-1&&s[x+1][y].v==v-1)
{
c=s[x+1][y];
setxy(y*2,x);
x++;
printf("");
setxy(y*2,x);
printf("◎");
Sleep(500);
continue;
}
elseif(y-1>=0&&s[x][y-1].v==v-1)
{
c=s[x][y-1];
setxy(y*2,x);
y--;
printf("");
setxy(y*2,x);
printf("◎");
Sleep(500);
continue;
}
elseif(y+1<=col-1&&s[x][y+1].v==v-1)
{
c=s[x][y+1];
setxy(y*2,x);
y++;
printf("");
setxy(y*2,x);
printf("◎");
Sleep(500);
continue;
}
}
printf(" returngo ");
system("pause");
}

voidGetMapFromFile()
{
inti,j,x,y,len;
charch[50]={''};
FILE*fp=fopen("e:\map1.txt","r");
if(fp==NULL)
{
printf("openfilefailed. ");
return;
}
x=0;

while(!feof(fp))
{
fgets(ch,50,fp);
row++;
}
col=strlen(ch);
fseek(fp,0L,SEEK_SET);
while(!feof(fp))
{
fgets(ch,50,fp);
if(s==NULL)
{
len=strlen(ch);
for(i=len-1;i>0;i--)
{
if(ch[i]!='0'&&ch[i]!='1')
{
ch[i]='';
}
else
{
break;
}
}
len=strlen(ch);
s=(PT**)malloc(sizeof(PT*)*row);
for(j=0;j<len;j++)
{
*(s+j)=(PT*)malloc(sizeof(PT)*len);
}
}
y=0;
for(i=0;i<len;i++)
{
s[x][y].type=ch[i]-48;
s[x][y].x=x;
s[x][y].y=y;
s[x][y].v=-1;
y++;
}
x++;
}
start=s[row-2][1];
end=s[row-2][len-2];
fclose(fp);
}

intmain()
{
GetMapFromFile();
inti,j;
intx,y;
x=end.x;
y=end.y;
s[x][y].v=0;
stack_in(end);
fun();
c=start;
prt();
go(start.x,start.y);
return0;
}

E. 求解c语言一递归迷宫问题

给你给伪算法:(设坐标为x,y,坐标向右和下延生。)
函数:

判断当前是不是(7,7),如果是,表示走出迷宫。打印轨迹
1 尝试往左先走一步(x-1,如果x小于0,或者对应位置标识为阻塞)
2 1如果成功,用本函数递归调用左走一步的坐标,并记下当前位置到轨迹列表。
3 尝试往前先走一步(y+1,如果y小于0,或者对应位置标识为阻塞)
4 3如果成功,用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。
5 尝试往右先走一步(x+1,如果x小于0,或者对应位置标识为阻塞)
6 5如果成功,用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。
如果是(0,0),表示没有合适的路径可走出迷宫。
如果不是(0,0),将轨迹列表最后一位弹出。

F. 迷宫问题,C语言

#include<stdio.h>
int main(void)
{
int maze[100][100];
int MAZE[100][100];
int m,n;
int p,q;

printf("输入迷宫的行数m,列隐氏数n:\n");
scanf("%d%d",&m,&n);
for(p=0;p<=n+1;p++){
maze[0][p]=1;
maze[m+1][p]=1;
}
for(p=1;p<=m;p++){
maze[p][0]=1;
maze[p][n+1]=1;
printf("宽做输入第%d行迷宫:\n",p);
for(q=1;q<=n;q++){
scanf("%d",&maze[p][q]);
MAZE[p][q]=maze[p][q];

}
}

struct location{
int row;
int col;
}way[100];

int movehoriz[8]={-1,0,1,1,1,0,-1,-1};
int movevert[8]={1,1,1,0,-1,-1,-1,0};

int endrow=m;
int endcol=n;

way[0].row=1;
way[0].col=1;
int start=3;

int i=0;
int k;
int j;
int found=0;

while(!found){
for(k=start;k<start+8;k++){
if((maze[way[i].row+movevert[k%8]][way[i].col+movehoriz[k%8]]==0)&&((i==0)||((way[i].row!=way[i-1].row)||(way[i].col!=way[i-1].col)))){
way[i+1].row=way[i].row+movevert[k%8];
way[i+1].col=way[i].col+movehoriz[k%8];
i++;
start=(k+5)%8;
break;
}
if((way[i].row==endrow)&&(way[i].col==endcol)){
break;
}
if((maze[way[i].row+movevert[k]][way[i].col+movehoriz[k]]==0)&&(way[i].row==way[i-1].row)&&(way[i].col==way[i-1].col)){
way[i].row=0;
way[i].col=0;
maze[way[i].row][way[i].col]=1;
i--;
start=(start+4)%8;
}

}
if(k>=start+8){
break;
}
if((way[i].row==endrow)||(way[i].col==endcol)){
found=1;
break;
}

}

if(found){
for(j=0;j<=i;j++){
printf("maze[%d][%d]\n",way[j].row,way[j].col);
}
}
else{
printf("The maze does not have a path\n");
}

}

QQ:366597114 不一定完全对。也许有灶巧散小错误。有问题可以来问我哈

G. 如何用C语言实现求迷宫的最短路径

#include<stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定义迷宫,0表示能走的块,1表示不能走,在外围加上一圈不能走的块
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct
{
int i,j; //块的位置
int pre; //本路径中上一块在队列中的下标
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front<=rear&&!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xe&&j==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di<4;di++)
{
switch(di) //四个方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循环
}
}
}
return 0;
}

void print(int n) //输出 路径算法
{
int k=n,j,m=1;
printf("\n");
do //将输出的路径上的所有pre改为-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宫最短路径如下:\n");
k=0;
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(m%5==0)
printf("\n");
m++;
}
k++;
}
printf("\n");
}
int main()
{
mgpath(1,1,M,N);
system("pause");
return 0;
}

H. C语言迷宫找出路问题。帮画个流程图。比如下图

/*
算法
*/

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#defineM4//行数
#defineN4//列数
#defineMaxSize100//栈最多元素个数
intmg[M+2][N+2]={//一个迷宫,其四周要加上均为1的外框,1为墙
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,1,1,0,1,1},
{1,0,1,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
structmigong{
inti;//路径横坐标
intj;//路径纵坐标
intdi;//方向
}Stack[MaxSize];//定义栈
inttop=-1;//栈顶指针
voidmgpath(){//路径为:(1,1)->(M,N)从起点1,1走到出口m,n
inti,j,di,find,k;
top++;
Stack[top].i=1;
Stack[top].j=1;
Stack[top].di=-1;
mg[1][1]=-1;//初始结点进栈
while(top>-1){//栈不空时循环
i=Stack[top].i;
j=Stack[top].j;
di=Stack[top].di;
if(i==M&&j==N){//找到了出口,输出路径
printf("迷宫出口路径如下: ");
for(k=0;k<=top;k++){
printf("(%d,%d,%d)",Stack[k].i,Stack[k].j,Stack[k].di);
if((k+1)%5==0)//输出时每5个结点换一行
printf(" ");
}
printf(" ");
break;
}
find=0;
while(di<4&&find==0){//找下一个可走结点
di++;
switch(di){
case0:i=Stack[top].i-1;j=Stack[top].j;break;//上面
case1:i=Stack[top].i;j=Stack[top].j+1;break;//右边
case2:i=Stack[top].i+1;j=Stack[top].j;break;//下面
case3:i=Stack[top].i;j=Stack[top].j-1;break;//左边
}
if(mg[i][j]==0)
find=1;//找到通路
}
if(find==1){//找到了下一个可走结点
Stack[top].di=di;//修改原栈顶元素的di值
top++;//下一个可走结点进栈
Stack[top].i=i;
Stack[top].j=j;
Stack[top].di=-1;
mg[i][j]=-1;//避免重复走到该结点
}
else{
mg[Stack[top].i][Stack[top].j]=0;//让该位置变为其他路径的可走结点
if(Stack[top].i==1&&Stack[top].j==1)
{
printf("该迷宫问题没有解! ");
break;
}
top--;
}
}
}
intmain(){
printf(" ");
printf("迷宫解题问题中心欢迎您 ");
printf(" ");
printf("设计者:么么哒 ");
printf(" ");
printf("****************************************************************************** ");
printf(" ");
mgpath();
return0;
}