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