æ±è¿·å®«é®é¢å°±æ¯æ±åºä»å
¥å£å°åºå£çææè·¯å¾ãå¨æ±è§£æ¶,é常ç¨çæ¯â穷举æ±è§£âçæ¹æ³,å³ä»å
¥å£åºå,顺æä¸æ¹åååè¯æ¢,è¥è½èµ°é,å继ç»å¾åèµ°ï¼å¦å沿åè·¯éå,æ¢ä¸ä¸ªæ¹åå继ç»è¯æ¢,ç´è³ææå¯è½çéè·¯é½è¯æ¢å®ä¸ºæ¢
#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
[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è¿æ¯ä¸éæ»´o(â©_â©)o...
}
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
[N])
{
int i,j;
int m,n; //迷宫è¡,å
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("ä½ å»ºç«ç迷宫为o(â©_â©)o...\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
[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); //find path
system("PAUSE");
}
温馨提示:答案为网友推荐,仅供参考