c语言迷宫最短路径

‘壹’ 迷宫最短路径 深度搜索问题 如果找不到出路要输出一个负一应该怎么办c语言问题啊

C语言问题还是真的比较难的。

‘贰’ 迷宫问题算法设计！！急急急（c语言）

额，又是课程设计。。。
迷宫类算法，用栈，队列来做。不过一般来队列，因为队列能够在较短时间内求出最短路径。
在网上搜下，很多的。。
你的要求很难达到。。。

‘叁’ C语言迷宫,最短路径,排队问题

利用BFS算法 应该可以解决这个问题 介绍看一下图论相关书籍

‘肆’ c语言版数据结构，要求用队列求解迷宫最短路径。

哦

‘伍’ c语言的迷宫问题，就是1不可以走，0可以走的那道，是深搜好做还是广搜好做

广收的话路径是最短的，深收也行。

‘陆’ 数据结构迷宫问题（c语言）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 10//迷宫包括外墙最大行列数目
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define STACK_INIT_SIZE 100 //存储空间初始分配量

typedef struct{
int r,c;
} PosType;//迷宫中r行c列的位置

typedef struct MazeType{
int r;
int c;
char arr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
}MazeType; //迷宫类型

typedef struct{
int step; // 当前位置在路径上的“序号”
PosType seat; //当前的坐标位置
int di; //往下一坐标位置的方向
}SElemType;

typedef struct NodeType{
SElemType data;
NodeType *next;
}NodeType,*LinkType;//结点类型
typedef struct SqStack{
LinkType top;
int stacksize;
}SqStack; //栈类型

PosType start;
PosType end;
MazeType maze;
bool found;

Status InitStack(SqStack &S){
S.top=(LinkType)malloc(sizeof(NodeType));
S.top->next=NULL;
S.stacksize=0;
return OK;
}//InitStack;

Status Push(SqStack &S,SElemType &e){
LinkType p;
p=(NodeType*)malloc(sizeof(NodeType));
if(!p) return ERROR;
p->data=e;
p->next=S.top;
S.top=p;
S.stacksize++;
//S.top=S.base+S.stacksize;
//S.top->data=e;
return OK;
}//Push

Status StackEmpty(SqStack S){
if(S.top->next==NULL) return OK;
return ERROR;
}//StackEmpty

Status Pop(SqStack &S,SElemType &e){
LinkType p;
if(StackEmpty(S)) return ERROR;
p=S.top;
e=p->data;
S.top=S.top->next;
S.stacksize--;
free(p);
return OK;
// 栈顶元素出栈
}//Pop

Status DestroyStack(SqStack &S){//销毁栈S,
LinkType p;
while(S.top!=NULL){
p=S.top;
S.top=S.top->next;
free(p);
}//while
if(S.top==NULL) return OK;
else return ERROR;
}//DestroyStack

Status MarkPrint(MazeType &maze,PosType curpos){
maze.arr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
return OK;
}//Markprint曾走过但不是通路标记并返回OK

Status FootPrint(MazeType &maze,PosType curpos){
maze.arr[curpos.r][curpos.c]='*';//"*"表示可通
return OK;
}//FootPrint

PosType NextPos(PosType &curpos,int i){
PosType cpos;
cpos=curpos;
switch(i){ //1.2.3.4分别表示东,南,西,北方向
case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(ERROR);
}//switch
return cpos;
}//Nextpos

Status Pass(MazeType &maze, PosType curpos){
/*for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
printf("%4c",maze.arr[i][j]);
}
printf("\n");
}*/
//char a=' ';
//printf("%4d",a);
//printf("%d,%d",curpos.r,curpos.c);
//printf("%4c",maze.arr[1][1]);
if(maze.arr[curpos.r][curpos.c]==' '){//当前位置可通
//printf("go");
return TRUE;
}//if
else{
//printf("go");
return FALSE;
}//else
}//Pass

void InitMaze(MazeType &maze, char a[MAXLEN][MAXLEN], int row, int col){
//printf("go");
maze.r=row;
maze.c=col;
//printf("%d,%d",row,col);
for(int i=0;i<=col+1;i++){a[0][i]='1';a[row+1][i]='1';}
//printf("go");
for(i=0;i<=row+1;i++){a[i][0]='1';a[i][col+1]='1';}
//printf("go");
/*for(i=0;i<10;i++){
for(int j=0;j<10;j++){
printf("%4c",a[i][j]);
}
printf("\n");
}
*/
for(i=0;i<=maze.r+2;i++){
for(int j=0;j<maze.c+2;j++){
if(a[i][j]=='1') maze.arr[i][j]='#';
//if(a[i][j]==0) maze.arr[i][j]=' ';
else maze.arr[i][j]=' ';
}//for
}//for
}//InitMaze

Status MazePath(MazeType &maze,PosType start,PosType end)
{//求解迷宫maze中，从入口start到出口end的一条路径，
//若存在则返回TRUE,否则返回FALSE
PosType curpos;
int curstep;
SqStack S;
SElemType e;

InitStack(S);
curpos=start;//设定“当前位置”为“入口位置”
curstep=1; //探索第一步
found=false;

do{
if(Pass(maze,curpos))
{
//当前位置可以通过，即是未曾走到过的通道块留下足迹
FootPrint(maze,curpos);//做可以通过的标识

e.step=curstep;
e.seat=curpos;
e.di=1;//为栈顶元素赋值

if(Push(S,e)!=OK) return ERROR;
if(curpos.r==end.r && curpos.c==end.c) found=true;//如果到达终点返回true

else{
curpos=NextPos(curpos,1);//下一位置是当前位置的东邻
curstep++;//探索下一步
}//else
}//if

else
if(StackEmpty(S)!=1)
{
Pop(S,e);
while(e.di==4 && !StackEmpty(S))
{

MarkPrint(maze,e.seat);
Pop(S,e);
curstep--;
}//while
if(e.di<4)
{
e.di++;
Push(S,e);//换下个方向探索
curpos=NextPos(e.seat,e.di);
}//if
}//if
}while(StackEmpty(S)!=1&&!found);
DestroyStack(S);
if(found)
return true;
else
return false;//没有找到路径

}//MazePath

void PrintMaze(MazeType &maze){
//将标记路径信息的迷宫输出到终端(包括外墙)
for(int i=0;i<=maze.r+2;i++){
for(int j=0;j<=maze.c+2;j++){
printf("%4c",maze.arr[i][j]);//输出迷宫
}//for
printf("\n");
}//for
}//PrintMaze

void Initialization(){
system("cls");
printf("********************************************************");
printf("\n*CreatMaze--c MazePath--m PrintMaze--p Quit--q*");
printf("\n********************************************************");
}//Initialization

void ReadCommand(char &cmd){
do{
if(cmd=='c'||cmd=='C'){
printf("\n********************************************************");
printf("\n*Enter a operation :m或M *");
printf("\n*退出--Enter a operation :q或Q *");
printf("\n********************************************************");
}//if
else if(cmd=='m'||cmd=='M'){
printf("\n********************************************************");
printf("\n*Enter a operation :p或P *");
printf("\n*退出--Enter a operation :q或Q *");
printf("\n********************************************************");
}//else if
else if(cmd=='0'){
printf("\n********************************************************");
printf("\n*Enter a operation :c或P *");
printf("\n*退出--Enter a operation :q或Q *");
printf("\n********************************************************");
}
printf("\n\n Operration:-");
cmd=getchar();
}while(!(cmd=='c'||cmd=='C'||cmd=='m'||cmd=='M'||cmd=='p'||cmd=='P'||cmd=='q'||cmd=='Q'));
}//ReadCommand

void Interpre(char cmd){
//MazeType maze;//开始的时候定义在这个地方，不是全局的，调用出现了问题。
//PosType start;//开始的时候定义在这个地方，不是全局的，调用出现了问题。
//PosType end;//开始的时候定义在这个地方，不是全局的，调用出现了问题。
switch(cmd){
case 'C':
case 'c':{
int rnum, cnum, i=0,m=1,n=1;
char a2[MAXLEN][MAXLEN];
char input[1];
char data[100000];
printf("\n请输入迷宫数据文件名！\n");
//printf("go");
scanf("%s",input);
FILE *fp;
fp=fopen(input,"r");
//printf("go");
if(!fp){
printf("\n不能打开文件\n");
break;
}//if
//printf("go");
while(!feof(fp)){
fscanf(fp,"%s",&data[i]);
if(i==0){rnum=(int)data[i]-(int)'0';/*printf("%d",rnum);*/}
if(i==1){cnum=(int)data[i]-(int)'0';/*printf("%d",rnum);*/}
if(i>=2){
if(n>cnum){m++;n=1;}
a2[m][n]=data[i];
//printf("%d",a2[m][n]);
n++;
}//if
i++;
}//while
fclose(fp);
//printf("go");
InitMaze(maze, a2, rnum, cnum);
printf("\n迷宫建立完成！！\n");
//PrintMaze(maze);
break;
}//case
case 'M':
case 'm':{
printf("\n请输入迷宫入口的坐标，以空格为间隔:--");
scanf("%d %d",&start.r,&start.c);
printf("\n请输入迷宫出口的坐标，以空格为间隔:--");
scanf("%d %d",&end.r,&end.c);
//printf("%d,%d,%d,%d",start.r,start.c,end.r,end.c);
//PrintMaze(maze);
MazePath(maze, start, end);
//PrintMaze(maze);
break;
}//case
case 'P':
case 'p':{
if(found){
printf("\n求解迷宫的结果如下--\n");
PrintMaze(maze);
}//if
else{
printf("\n找不到路径！\n");
}//else
}//case
}//switch
}//Interpre

void main(){
char cmd='0';
Initialization();
//cmd=getchar();
do{
ReadCommand(cmd);
Interpre(cmd);
}while(cmd!='q'&&cmd!='Q');
}//main