Question

迷宫问题，C语言

以一个 m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论
起点就是方阵中的（1，1）终点就是（m-1，n-1）

Answer 1

#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 不一定完全对。也许有小错误。有问题可以来问我哈

Answer 2

这个要用到数据结构中讲到的堆栈，建议你去找一本“数据结构”的教材，基本上每本书都会讲到这个十分经典的问题，上面的算法分析都很详细，但是理解起来还是有点困难，你必须慢慢看，反复琢磨。我也是琢磨了好多次才弄懂

Answer 3

#include<stdio.h>
#define MAX_STACK_SIZE 100
#define MAX_SIZE 10
typedef struct{
short int vert;
short int horiz;
}offsets;
offsets move[8];
typedef struct{
short int row;
short int col;
short int dir;
}element;
element stack[MAX_STACK_SIZE];
int maze[MAX_SIZE][MAX_SIZE],mark[MAX_SIZE][MAX_SIZE];
int TRUE=1,FALSE=0,EXIT_ROW,EXIT_COL,top;
void push(int *top,element item);
element pop(int *top);
void main()
{
move[0].vert=-1; move[0].horiz=0;
move[1].vert=-1; move[1].horiz=1;
move[2].vert=0; move[2].horiz=1;
move[3].vert=1; move[3].horiz=1;
move[4].vert=1; move[4].horiz=0;
move[5].vert=1; move[5].horiz=-1;
move[6].vert=0; move[6].horiz=-1;
move[7].vert=-1; move[7].horiz=-1;
int i,j,row,col,next_row,next_col,dir,found=FALSE;
element position;
printf("输入迷宫的行数与列数:\n");
scanf("%d%d",&row,&col);
for(i=0;i<=row+1;i++)
maze[i][0]=1;
for(i=0;i<=col+1;i++)
maze[0][i]=1;
for(i=row+1;i>=0;i--)
maze[i][col+1]=1;
for(i=col+1;i>=0;i--)
maze[row+1][i]=1;
for(i=1;i<=row;i++)
for(j=1;j<=col;j++)
scanf("%d",&maze[i][j]);
EXIT_ROW=row;
EXIT_COL=col;
mark[1][1]=1;
top=0;
stack[0].row=1;
stack[0].col=1;
stack[0].dir=1;
while(top>-1&&!found){
position=pop(&top);
row=position.row;
col=position.col;
dir=position.dir;
while(dir<8&&!found){
next_row=row+move[dir].vert;
next_col=col+move[dir].horiz;
if(next_row==EXIT_ROW&&next_col==EXIT_COL)
found=TRUE;
else if(!maze[next_row][next_col]&&!mark[next_row][next_col]){
mark[next_row][next_col]=1;
position.row=row;
position.col=col;
position.dir=++dir;
push(&top,position);
row=next_row;
col=next_col;
dir=0;
}
else ++dir;
}
}
if(found){
printf("The path is:\n");
printf("row col\n");
for(i=0;i<=top;i++)
printf("%2d%5d\n",stack[i].row,stack[i].col);
printf("%2d%5d\n",row,col);
printf("%2d%5d\n",EXIT_ROW,EXIT_COL);
}
else printf("The maze does not have a path\n");
}
void push(int *top,element item)
{
if(*top>=MAX_STACK_SIZE-1) printf("The stack is full\n");
else stack[++*top]=item;
}
element pop(int *top)
{
if(*top==-1){
printf("The stack is empty\n");
return stack[-1];
}
else return stack[(*top)--];
}

Answer 4

#include"stdio.h"
#define M 6
#define N 8
#define MAX 100
typedef struct
{ int x;
int y;
}item;
typedef struct
{ int x,y,d;
}sanyuan;
typedef struct
{ sanyuan elem[MAX];
int top;
}sqstack;
void Initstack(sqstack *s)
{s->top=-1;}
int stackempty(sqstack *s)
{if(s->top==-1) return 1;
else return 0;}
void push(sqstack *s,sanyuan e)
{if(s->top==MAX-1)
{printf("stack is full\n");
return;}
s->top++;s->elem[s->top]=e;}
sanyuan pop(sqstack *s,sanyuan e)
{
e=s->elem[s->top];
s->top--;
return e;
}
void printpath(sqstack *s)
{sanyuan temp;
printf("(%d,%d)<==",M,N);
while(!stackempty(s))
{temp=pop(s,temp);
printf("(%d,%d)<==",temp.x,temp.y);
}
printf("\n");
}
int mazepath()
{
int maze[M+2][N+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,1,0,1,1,1,1,1},{1,0,1,0,0,0,0,0,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,0,1,1,0,0,0,1},{1,0,1,1,0,0,1,1,0,1},{1,1,1,1,1,1,1,1,1,1}};
item move[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
sqstack *s;sanyuan temp;
int x,y,d,i,j;
Initstack(s);
temp.x=1;temp.y=1;temp.d=-1;
push(s,temp);
while(!stackempty(s))
{pop(s,temp);
x=temp.x;y=temp.y;d=temp.d+1;
while(d<8)
{i=x+move[d].x;
j=y+move[d].y;
if(maze[i][j]==0)
{temp.x=x;temp.y=y;temp.d=d;
push(s,temp);
x=i;y=j;
maze[x][y]=-1;
if(x==M&&y==N)
{printpath(s);
return 1;
}
else d=0;
}
else d++;
}
}
return 0;
}

void main()
{

mazepath();
}