查人人中国名人网炽凰朱雀图片:一个c程序的迷宫问题:
来源：百度文库 编辑：查人人中国名人网 时间：2024/04/27 17:30:09
typedef struct {
short int row;
short int col;
short int dir;
}element;
element stack[MAX];
typedef struct{
short int vert;
short int horiz;
}offsets;
offsets move[8];
int top=-1;
int maze[9][6],mark[MAX][MAX];
int EXIT_ROW;
int EXIT_COL;
void add(int *top,element a);
element delete(int *top);
void path(void);
void chushi(offsets move[8]);
main()
{
int i,j;
chushi(move);
printf("The maze is:"); (输入迷宫:最外围必须是1)
for(i=0;i<9;i++)
for(j=0;j<6;j++)
scanf("%d",&maze[i][j]);
for(i=0;i<9;i++)
{ printf("\n");
for(j=0;j<6;j++)
printf("%d",maze[i][j]);
}
EXIT_ROW=i-2;
EXIT_COL=j-2;
printf("\n");
path();
}
void add(int *top,element a)(入栈函数)
{
stack[++*top]=a;
}
element delete(int *top)
{return stack[(*top)--];}
void path(void) (搜索出口)
{
int i, row, col, next_row, next_col, dir, found = 0;
element position;
mark[1][1] = 1; top = 0;
stack[0].row = 1; stack[0].col = 1; stack[0].dir = 1;
while ( top > -1 && !found ) {
position = delete(&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 = 1;
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;
add(&top, position);
row = next_row; col = next_col; dir = 0;
}
else ++dir;
}
}
if ( found==1 ) {
printf ("The path is:\n");
printf ("row col\n");
printf("\n");
for ( i = 0; i <= top; i++ )
printf ("%2d %5d", stack[i].row, stack[i].col);
printf("\n");
printf ("%2d %5d\n",row,col);
printf("\n");
printf ("%2d%5d\n",EXIT_ROW,EXIT_COL);
}
else printf ("The maze does not have a path\n");
}
void chushi(offsets move[8]) (初始化8个方向)
{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;
}
为什么能运行,但却输不出path.
没少函数,单步运行后,问题出在EXIT_ROW,EXIT_COL
你写的跟我的差不多，不过我的初始化简单些，同时对于访问过的元素的标记不一样。
你的程序里面我感觉是没有回溯，不过写得太长了，没有太细看，你看看我的吧，这个结果正确，你可以参考一下。
#define MAX 1000
#include<stdio.h>
main()
{
int MAZE[8][11]={{1,1,1,1,1,1,1,1,1,1,1},{1,0,1,0,0,0,1,1,0,0,1},{1,1,0,0,0,1,1,0,1,1,1},{1,0,1,0,0,0,0,0,1,1,1},{1,1,1,0,1,1,1,1,0,1,1},{1,1,1,0,1,0,0,1,0,0,1},{1,0,0,0,1,1,0,1,1,0,1},{1,1,1,1,1,1,1,1,1,1,1}};
int MOVE[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int i,j,k,g,h,top=0,p;
int STACK[MAX][3];
int flag=0;
MAZE[1][1]=2;
i=STACK[0][0]=1;
j=STACK[0][1]=1;
k=STACK[0][2]=3;
while(top>=0)
{
if(flag==0)
{
i=STACK[top][0];
j=STACK[top][1];
k=0;
}
else if(flag==1)
{
i=STACK[--top][0];
j=STACK[top][1];
k=STACK[top][2]+1;
}
flag=1;
while(k<8)
{
g=i+MOVE[k][0];
h=j+MOVE[k][1];
if(g==6&&h==9&&MAZE[g][h]==0)
{
printf("a road is find !\n");
for(p=0;p<=top;p++)
printf("(%3d,%3d)--> ",STACK[p][0],STACK[p][1]);
printf("(%3d,%3d)",STACK[top][0],STACK[top][1]);
return 1;
}
if(MAZE[g][h]==0)
{
MAZE[g][h]=2;
STACK[++top][0]=g;
STACK[top][1]=h;
STACK[top][2]=k;
i=g;
j=h;
k=0;
flag=0;/*flag=0表示下面有点可以继续查找,flag=1表示需要回溯*/
break;
}
k++;
}
}
if(top==0)
printf("haven't find any road!");
getch();
}
我不明白哦
单步跟踪一下就知道了
好象少函数
为什么出这样的问题?太伤人了,我一点都不懂、、、