¸Ð¾õ×Ô¼ºÐ´µÄÕâ¸ö½á¹¹Óе㸴ÔÓ~²Î¿¼Ò»Ï¾ͿÉÒÔÁË~
»¹ÓÐͨÓÃÁ´±í²Î¿¼Í·Îļþ"List.h"
https://bbs.bccn.net/thread-476405-1-1.html
30Â¥´úÂë~
³ÌÐò´úÂ룺
#include"List.h"
#include<windows.h>
#include<conio.h>
#ifndef MAXSIZE
#define MAXSIZE 10 //ÃÔ¹¬µÄ×î´ó³¤¶È
#endif
typedef char MAP; //×Ô¶¨ÒåÃÔ¹¬µØͼ
typedef enum Visit
{
DISCOVER,
COVER,
}Visit;
typedef enum DIRECTION //ö¾ÙËĸö·½Ïò
{
UP,
DOWN,
LEFT,
RIGHT,
}DIRECTION;
typedef struct Point //¶¨Òå×ø±ê¶Ô
{
int x; //ºá×ø±ê
int y; //×Ý×ø±ê
}Point;
typedef struct Graph //´¢´æÃÔ¹¬µØͼ½á¹¹Ìå
{
Visit visit[sizeof(DISCOVER)];
Visit visit_This;
MAP data; //¼Ç¼´¢´æÊý¾Ý
}Graph;
typedef struct Maze //ÃÔ¹¬ÐÅÏ¢
{
Point start; //Æðµã×ø±ê
Point end; //ÖÕµã×ø±ê
int d;
Graph graph[MAXSIZE][MAXSIZE]; //ÃÔ¹¬½á¹¹ÐÅÏ¢
}Maze,*PMaze;
typedef int MAZE_MOVE(PMaze maze,Point* point); //×Ô¶¨Òå±äÁ¿
void Maze_Init(PMaze maze,MAP map[][MAXSIZE+1]); //³õʼ»¯ÃÔ¹¬
void Maze_Print(PMaze maze); //´òÓ¡ÃÔ¹¬
void Maze_Print_Road(PList p,PMaze maze); //´òӡ·
void Maze_Find_Road(PMaze maze); //Ñ°ÕÒÃÔ¹¬³ö¿Ú·¾¶
MAZE_MOVE Maze_Move_Up; //¶ÔËĸö·½ÏòµÄÒƶ¯½øÐÐÅжÏ
MAZE_MOVE Maze_Move_Down;
MAZE_MOVE Maze_Move_Left;
MAZE_MOVE Maze_Move_Right;
MAZE_MOVE Maze_Judge_Win; //ÅжÏÊÇ·ñÕÒµ½ÖÕµã
void Print_COM(void* p); //×Ô¶¨Òå´òÓ¡º¯Êý
int main()
{
Maze maze={0};
MAP map[MAXSIZE][MAXSIZE+1]=
{
{"**********"},
{"* ** *"},
{"* *** ** *"},
{"* ** * *"},
{"* ** * *"},
{"* ** * *"},
{"* ** *"},
{"* ****** *"},
{"* ***** *"},
{"**********"},
};
system("cls");
Maze_Init(&maze,map);
Maze_Print(&maze);
Maze_Find_Road(&maze);
return 0;
}
void Maze_Init(PMaze maze,MAP map[][MAXSIZE+1]) //³õʼ»¯ÃÔ¹¬
{
int i=0;
int j=0;
int k=0;
maze->start.x=1; //³õʼ»¯Æðµã×ø±ê
maze->start.y=1;
maze->end.x=8; //³õʼ»¯ÖÕµã×ø±ê
maze->end.y=8;
maze->d=sizeof(DISCOVER);
for (i=0;i<MAXSIZE;++i)
for (j=0;j<MAXSIZE;++j)
{
maze->graph[i][j].data=map[i][j];
for (k=0;k<maze->d;++k)
maze->graph[i][j].visit[k]=DISCOVER;
maze->graph[i][j].visit_This=DISCOVER; //±íʾ¸Ã¸ñûÓÐ×ß¹ý
}
}
void Maze_Print(PMaze maze)
{
int i=0;
int j=0;
for (i=0;i<MAXSIZE;++i)
{
for (j=0;j<MAXSIZE;++j)
putchar(maze->graph[i][j].data);
puts("");
}
}
void Maze_Find_Road(PMaze maze) //Ñ°ÕÒÃÔ¹¬³ö¿Ú·¾¶
{
PList p=NULL;
Point point= //»ñÈ¡Æðµã×ø±ê
{
maze->start.x,
maze->start.y,
};
MAZE_MOVE *move[sizeof(DISCOVER)]={0}; //¶¨ÒåËĸö·½ÏòµÄÖ¸Õ뺯ÊýÊý×é
int win=0; //ÅжÏÊÇ·ñÓгö¿Ú
move[UP]=Maze_Move_Up;
move[DOWN]=Maze_Move_Down;
move[LEFT]=Maze_Move_Left;
move[RIGHT]=Maze_Move_Right;
List_Fun.Creat_Link(&p,&point,sizeof(Point)); //´´½¨Ò»¸öÕ»
List_Fun.Insert_Rear(p,&point); //Æðʼ×ø±êÈëÕ»
maze->graph[point.x][point.y].visit_This=COVER; //±ê¼Ç´Ë×ø±ê±»±éÀú¹ý
printf("Æðµã×ø±ê:(%d,%d)\n",point.x,point.y);
printf("ÖÕµã×ø±ê:(%d,%d)\n",maze->end.x,maze->end.y);
while (!List_Fun.Empty_List(p))
{
int i=0;
int len=sizeof(DISCOVER);
for (i=0;i<len;++i)
{
if (move[i](maze,&point)&&((win=Maze_Judge_Win(maze,&point))==0))
{
List_Fun.Insert_Rear(p,&point); //ÈëÕ»
i=-1;
//¶ÔÐÂλÖÃÖØÐÂÅжÏ
}
if (win==1)
{
List_Fun.Insert_Rear(p,&point);
break;
}
}
if (win==1)
{
puts("Éî¶ÈËÑË÷·ÏßÈçÏÂ:");
List_Fun.Println_List(p,Print_COM); //Êä³öÁ´±íÊý¾Ý
break;
}
List_Fun.Del_Rear(p,&point); //³öÕ»
}
if (List_Fun.Empty_List(p))
puts("ÕÒ²»µ½³ö¿Ú!");
else
printf("¹²×ßÁË%d²½\n",p->length);
while (!List_Fun.Empty_List(p))
{
List_Fun.Remove_Front(p,&point);
maze->graph[point.x][point.y].data='o';
}
if (win)
{
puts("Çë°´ÈÎÒâ¼üÊä³öÃÔ¹¬Â·Ïß:");
getch();
Maze_Print(maze);
}
List_Fun.Del_List(&p,1); //ÊÍ·ÅÕ»
}
int Maze_Move_Up(PMaze maze,Point* point) //×Ô¶¨Òå±äÁ¿
{
if (maze->graph[point->x][point->y].visit[UP]==COVER)
return 0;
if (point->x-1<0||maze->graph[point->x-1][point->y].data=='*')
return 0;
maze->graph[point->x][point->y].visit[UP]=COVER;
maze->graph[point->x][point->y].visit_This=COVER;
--point->x;
maze->graph[point->x][point->y].visit[DOWN]=COVER; //¶Ô·µ»Ø·¾¶½øÐд¦Àí
return 1;
}
int Maze_Move_Down(PMaze maze,Point* point) //×Ô¶¨Òå±äÁ¿
{
if (maze->graph[point->x][point->y].visit[DOWN]==COVER)
return 0;
if (point->x+1>MAXSIZE-1||maze->graph[point->x+1][point->y].data=='*'||maze->graph[point->x+1][point->y].visit_This==COVER)
return 0;
maze->graph[point->x][point->y].visit[DOWN]=COVER;
maze->graph[point->x][point->y].visit_This=COVER;
++point->x;
maze->graph[point->x][point->y].visit[UP]=COVER;
return 1;
}
int Maze_Move_Left(PMaze maze,Point* point) //×Ô¶¨Òå±äÁ¿
{
if (maze->graph[point->x][point->y].visit[LEFT]==COVER)
return 0;
if (point->y-1<0||maze->graph[point->x][point->y-1].data=='*'||maze->graph[point->x][point->y-1].visit_This==COVER)
return 0;
maze->graph[point->x][point->y].visit[LEFT]=COVER;
maze->graph[point->x][point->y].visit_This=COVER;
--point->y;
maze->graph[point->x][point->y].visit[RIGHT]=COVER;
return 1;
}
int Maze_Move_Right(PMaze maze,Point* point) //×Ô¶¨Òå±äÁ¿
{
if (maze->graph[point->x][point->y].visit[RIGHT]==COVER)
return 0;
if (point->y+1>MAXSIZE-1||maze->graph[point->x][point->y+1].data=='*'||maze->graph[point->x][point->y+1].visit_This==COVER)
return 0;
maze->graph[point->x][point->y].visit[RIGHT]=COVER;
maze->graph[point->x][point->y].visit_This=COVER;
++point->y;
maze->graph[point->x][point->y].visit[LEFT]=COVER;
return 1;
}
int Maze_Judge_Win(PMaze maze,Point* point) //×Ô¶¨Òå±äÁ¿
{
if (maze->end.x==point->x&&maze->end.y==point->y)
{
return 1;
}
return 0;
}
void Print_COM(void* p) //×Ô¶¨Òå´òÓ¡º¯Êý
{
int x=((Point* )p)->x;
int y=((Point* )p)->y;
printf("%-4d%-4d\n",x,y);
}
[´ËÌù×ÓÒѾ±»×÷ÕßÓÚ2017-6-4 21:55±à¼¹ý]