深度搜索：
/*迷宫的算法*/
/* 先建立迷宫（外围建筑围墙），设置入口和出口。建立链表，把第一个点（入口）入舰，同时做好
标记，以免重复入舰。a：判断舰顶元素的东面是否可通，若可通则将其入舰 ，同时做好标记，
以免重复入舰；若不通则判断舰顶元素的南面是否可通，依此操作至北面元素。
判断新的舰顶元素是否为出口 ，若是，则报告结束，并打印出路径；否则递归操作a：。
若舰顶元素其余三面皆不通 ，则将舰顶元素其重新设定为不通，以免以后再走弯路。然后退舰。
重复a；操作。
若退回到入口，则表示迷宫走不通，报告不通。*/
/*2005-4-22 梁见斌*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define NO 0
#define OVERFLOW 1
#define M 5
#define N 5
typedef struct poi{/*建立链表结构，存储每个路径点的有关数据；横坐标，纵坐标，所指方向和向下的指针*/
int x;
int y;
char *p;
struct poi *next;
} Point;
Point *head;
char a[100][200];
char FX[14]={'E','S','W','N','E','S','W', 'E','N','W','S','E','N','W',};/*存储方向*/
int MG_S[M+2][N+2], MG[M+2][N+2], In[2], Out[2], X_Y[2];/*分别存储迷宫，入，出口和当前坐标*/
int FX_Head, FX_Tail, row=0;
void Build(void);/*建立迷宫（外围建筑围墙），设置入口和出口*/
void B_IO(void);
void Copy(void);
void B_Head(int start);
void Go(void);/*主要操作，可递归调用*/
int Judge(void);/*判断下一结点是否可通，若可通则记录该点坐标，并返回可通标志*/
void Print(Point *head);/*打印行进路径*/
void Push(Point **head);/*将当前结点入舰，并做记号表示该点已经走过*/
void Pop(Point **head);/*将当前结点退舰，并做记号表示该点不通*/
void Pop_Or_No(int end);/*判断舰顶元素所指方向是否为北，若是则退舰，否则继续判断下一方向*/
void Store(Point *head);
void Pai_Xu(void);
void Xiao_Chu(void);
void Print_Total(void);
void Free(void);
void Change(Point **head);/*原链表从表头入出舰，故表头元素表示出口坐标，表尾元素表示入口坐标，
打印出来的路径图是反的，不合习惯，故用此函数将表头和表尾互换，其他
元素依次调换*/
int main(void)
{
int flag, i, m, n;
a: Build();
b: for(i=0; i<4; i++)
{
FX_Head = i; FX_Tail = i + 3;
if(i == 0)
B_IO();
Copy();
B_Head(FX_Head);
Go();
}
for(i=7; i<11; i++)
{
FX_Head = i; FX_Tail = i + 3;
Copy();
B_Head(FX_Head);
Go();
}
Pai_Xu();
Xiao_Chu();
Print_Total();
puts("do you want play again? 2 to change the I_O,1 to change the MG, 0 to quit: ");
scanf("%d", &flag);
if(flag == 1)
{
Free();
row = 0;
goto a;
}
else if(flag == 2)
{
Free();
row = 0;
goto b;
}
system("pause");
return 0;
}
void Build(void) /*建立迷宫（外围建筑围墙），设置入口和出口*/
{
int i, j;
puts("Build the MG");
for(i=1; i<=M; i++)
for(j=1; j<=N ; j++)
scanf("%d", &MG_S[i][j]);
fflush(stdin);
for(i=0; i<=M+1; i++) /*外围建筑围墙*/
{
MG_S[i][0] = 1;
MG_S[i][N+1] = 1;
}
for(j=0; j<=N+1; j++) /*外围建筑围墙*/
{
MG_S[0][j] = 1;
MG_S[M+1][j] = 1;
}
}
void B_IO(void)
{
int i, j;
for(i=0; i<=M+1; i++)/*输出迷宫图案*/
{
for(j=0; j<=N+1; j++)
printf("%d ", MG_S[i][j]);
printf("\n");
}
puts("Input the In Position");
for(i=0; i<2; i++)
scanf("%d", &In[i]);
puts("Input the Out Position");
for(i=0; i<2; i++)
scanf("%d", &Out[i]);
}
void Copy(void)
{
int i, j;
for(i=0; i<=M+1; i++) /*把原始迷宫复制到待测迷宫中*/
for(j=0; j<=N+1; j++)
MG[i][j] = MG_S[i][j];
}
void B_Head(int start)
{
head = (Point *)malloc(sizeof(Point));/*建立链表，把第一个点（入口）入舰*/
if(!head)
{
puts("出错了！");
getchar();
exit(OVERFLOW);
}
head->x = In[0];
head->y = In[1];
head->p = &FX[start];
head->next = NULL;
MG[head->x][head->y] = -1;/*表示该点已经走过*/
}
void Go(void) /*主要操作，可递归调用*/
{
int flag, i;
flag = Judge(); /*判断下一结点是否可通*/
if(flag == 3) /*判断新的舰顶元素是否为出口 ，若是，则报告结束，并打印出路径*/
{
Push(&head);
puts("\nsuccess！");
Change(&head);
Store(head);
}
else if(flag == 1)/*若可通则将其入舰 */
{
Push(&head);
Go();
}
else /*若不通，则判断舰顶元素所指方向是否为北，以便决定是否退舰*/
Pop_Or_No(FX_Tail);
}
int Judge(void) /*判断下一结点是否可通，若可通则记录该点坐标，并返回可通标志*/
{
switch( *(head->p))
{
case 'E': /*若舰顶元素指向东，则下一结点坐标为MG[head->x][head->y + 1]*/
{
if(head->x == Out[0] && head->y + 1 == Out[1])
{
X_Y[0] = head->x;
X_Y[1] = head->y + 1;
return 3; /*若下一结点可通，返回值1*/
}
else if(MG[head->x][head->y + 1] == 0)
{
X_Y[0] = head->x;
X_Y[1] = head->y + 1;
return 1; /*若下一结点可通，返回值1*/
}
else
return 0; /*若下一结点不可通，返回值0*/
}
case 'S':
{
if(head->x + 1 == Out[0] && head->y == Out[1])
{
X_Y[0] = head->x + 1;
X_Y[1] = head->y;
return 3; /*若下一结点可通，返回值1*/
}
else if(MG[head->x + 1][head->y] == 0)
{
X_Y[0] = head->x + 1;
X_Y[1] = head->y ;
return 1;
}
else
return 0;
}
case 'W':
{
if(head->x == Out[0] && head->y - 1 == Out[1])
{
X_Y[0] = head->x;
X_Y[1] = head->y - 1;
return 3; /*若下一结点可通，返回值1*/
}
else if(MG[head->x][head->y - 1] == 0)
{
X_Y[0] = head->x;
X_Y[1] = head->y - 1;
return 1;
}
else
return 0;
}
case 'N':
{
if(head->x - 1 == Out[0] && head->y == Out[1])
{
X_Y[0] = head->x - 1;
X_Y[1] = head->y;
return 3; /*若下一结点可通，返回值1*/
}
else if(MG[head->x-1][head->y] == 0)
{
X_Y[0] = head->x - 1;
X_Y[1] = head->y;
return 1;
}
else
return 0;
}
}
}
void Push(Point **head) /*将当前结点入舰，并做记号表示该点已经走过*/
{
Point *r, *s;
s = (Point *)malloc(sizeof(Point));
if(!s)
{
puts("出错了！");
getchar();
exit(OVERFLOW);
}
s->x = X_Y[0];
s->y = X_Y[1];
s->p = &FX[FX_Head];
MG[s->x][s->y] = -1;/*表示该点已经走过*/
s->next = *head;;
*head = s;
}
void Pop_Or_No(int end) /*判断舰顶元素所指方向是否为北，若是则退舰，否则继续判断下一方向*/
{
if(*(head->p) != FX[end])
{
(head->p)++;
Go();
}
else
{
if(head->x == In[0] && head->y == In[1]) /*若退回到入口，且入口指向北，则表示迷宫走不通*/
puts("fail！");
else
{
Pop(&head);
if(head->x == In[0] && head->y == In[1]) /*若退回到入口，且入口指向北，则表示迷宫走不通*/
{
if(*(head->p) != FX[end])
{
(head->p)++;
Go();
}
else
puts("fail！");
}
else
Pop_Or_No(end);
}
}
}
void Pop(Point **head) /*将当前结点退舰，并做记号表示该点不通*/
{
Point *s;
s = *head;
*head = s->next;
MG[s->x][s->y] = 1; /*记号表示该点不通*/
free(s);
}
void Change(Point **head) //原链表从表头入出舰，故表头元素表示出口坐标，表尾元素表示入口坐标，
{
Point *p, *q, *r; //打印出来的路径图是反的，不合习惯，故用此函数将表头和表尾互换，
//其他元素依次调换。
p = *head;
q = p->next;
while(q != NULL)
{
r = q->next;
q->next = p;
p = q;
q = r;
}
(*head)->next = NULL;
*head = p;
}
void Print(Point *head) /*打印行进路径*/
{
Point *r;
r = head;
while(r->next != NULL)
{
printf("(%d,%d)-> ", r->x, r->y);
r = r->next;
}
printf("(%d,%d)", r->x, r->y);
}
void Store(Point *head)
{
int i=0, flag=1;
char *s;
while(flag)
{
if(head->next != NULL)
{
a[row][i++] = '(';
a[row][i++] = (char)(head->x + 48);
a[row][i++] = ',';
a[row][i++] = (char)(head->y + 48);
a[row][i++] = ')';
a[row][i++] = '-';
a[row][i++] = '>';
a[row][i++] = ' ';
head = head->next;
}
else
flag = 0;
}
a[row][i++] = '(';
a[row][i++] = (char)(head->x + 48);
a[row][i++] = ',';
a[row][i++] = (char)(head->y + 48);
a[row][i++] = ')';
a[row][i++] = '\0';
row++;
}
void Pai_Xu()
{
int i, j, min;
char p[200];
for(i=0; i<row-1; i++)
{
min = i;
for(j=i+1; j<row; j++)
if(strlen(a[min]) > strlen(a[j]) )
min = j;
if(min != i)
{
strcpy(p, a[i]);
strcpy(a[i], a[min]);
strcpy(a[min], p);
}
}
}
void Xiao_Chu()
{
int i, j;
char p[200]="fail";
for(i=0; i<row-1; i++)
for(j=i+1; j<row; j++)
if(strcmp(a[i], a[j]) == 0)
strcpy(a[j], p);
}
void Print_Total()
{
int i;
puts("\nthe total root:");
for(i=0; i<row-1; i++)
if(strcmp(a[i], "fail") != 0)
puts(a[i]);
}
void Free(void)
{
Point *r;
while(head)
{
r = head;
head = head->next;
free(r);
}
}
广度搜索；
/*可以玩多次*/
/*迷宫的算法*/
/* 先建立迷宫（外围建筑围墙），设置入口和出口。建立链表队列，把第一个点（入口）入队，同时做好
标记，以免重复入队。
依次判断队头元素的东，南，西，北面是否为出口 ，若是则打印路径，并发出成功信号；
否则判断队头元素的该方向是否可通，若可通则将其入队 ，同时做好标记，
以免重复入队；
若未收到成功信号，则表示迷宫走不通，报告不通。*/
/*2005-4-22 梁见斌*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define NO 0
#define OVERFLOW 1
#define M 5
#define N 5
typedef struct poi{/*建立链表结构，存储每个路径点的有关数据；横坐标，纵坐标，向上的指针和向下的指针*/
int x, y;
struct poi *pre, *next;
} Point;
Point *head, *front, *rear;
int Z_X[7]={0, 1, 0, -1, 0, 1, 0}, Z_Y[7]={1, 0, -1, 0, 1, 0, -1};/*存储方向*/
int MG_S[M+2][N+2], MG[M+2][N+2], In[2], Out[2], row=0;/*分别存储迷宫，入，出口和当前坐标*/
char a[100][200];
void Build(void);/*建立迷宫（外围建筑围墙），设置入口和出口*/
void B_IO(void);
void Copy(void);
void Go(int m, int n) ;/*主要操作*/
void Print(Point *head);/*打印行进路径*/
Point *Change(void);
void Free(void);
void Store(Point *head);
void Pai_Xu(void);
void Xiao_Chu(void);
void Print_Total(void);
int main(void)
{
int flag, k;
Build(); /*建立迷宫（外围建筑围墙），设置入口和出口*/
a: B_IO();
k = 1;
b: Copy();
front = (Point *)malloc(sizeof(Point));/*建立链表，把第一个点（入口）入队*/
if(!front)
{
puts("出错了！");
getchar();
exit(OVERFLOW);
}
front->x = In[0];
front->y = In[1];
front->pre = NULL;
front->next = NULL;
MG[front->x][front->y] = -1;/*表示该点已经走过*/
rear = front;
head = front;
if(k == 1)
{
k++;
Go(0,3); /*主要操作*/
Free();
goto b;
}
else if(k == 2)
{
k++;
Go(1,4); /*主要操作*/
Free();
goto b;
}
else if(k == 3)
{
k++;
Go(2,5); /*主要操作*/
Free();
goto b;
}
else
Go(3,6); /*主要操作*/
Pai_Xu();
Xiao_Chu();
Print_Total();
puts("do you want play again? 1 to again, 0 to quit: ");
scanf("%d", &flag);
if(flag)
{
Free();
row = 0;
goto a;
}
system("pause");
return 0;
}
void Build(void) /*建立迷宫（外围建筑围墙），设置入口和出口*/
{
int i, j;
puts("Build the MG");
for(i=1; i<=M; i++)
for(j=1; j<=N ; j++)
scanf("%d", &MG_S[i][j]);
fflush(stdin);
for(i=0; i<=M+1; i++) /*外围建筑围墙*/
{
MG_S[i][0] = 1;
MG_S[i][N+1] = 1;
}
for(j=0; j<=N+1; j++) /*外围建筑围墙*/
{
MG_S[0][j] = 1;
MG_S[M+1][j] = 1;
}
}
void B_IO(void)
{
int i, j;
for(i=0; i<=M+1; i++)/*输出迷宫图案*/
{
for(j=0; j<=N+1; j++)
printf("%d ", MG_S[i][j]);
printf("\n");
}
puts("Input the In Position");
for(i=0; i<2; i++)
scanf("%d", &In[i]);
puts("Input the Out Position");
for(i=0; i<2; i++)
scanf("%d", &Out[i]);
}
void Copy(void)
{
int i, j;
for(i=0; i<=M+1; i++) /*把原始迷宫复制到待测迷宫中*/
for(j=0; j<=N+1; j++)
MG[i][j] = MG_S[i][j];
}
void Go(int m, int n) /*主要操作，可递归调用*/
{
Point *s, *p, *q;
int flag=0, fx, i, j;
while(front)
{
for(fx=m; fx<=n; fx++)
{
i = front->x + Z_X[fx];/*下一结点的坐标*/
j = front->y + Z_Y[fx];
if( i == Out[0] && j == Out[1])/*判断队头元素的该方向是否为出口 */
{
s = (Point *)malloc(sizeof(Point));
if(!s)
{
puts("出错了！");
getchar();
exit(OVERFLOW);
}
s->x = i;
s->y = j;
s->pre = front;
s->next = NULL;
q = rear;
rear->next = s;
rear = rear->next;
MG[s->x][s->y] = -1;/*表示该点已经走过*/
flag = 1; /*发出成功信号*/
p = Change();
Store(p);
rear = q;
}
else if(MG[i][j] == 0)/*判断队头元素的该方向是否可通，若可通则将其入队 */
{
s = (Point *)malloc(sizeof(Point));
if(!s)
{
puts("出错了！");
getchar();
exit(OVERFLOW);
}
s->x = i;
s->y = j;
s->pre = front;
s->next = NULL;
rear->next = s;
rear = rear->next;
MG[s->x][s->y] = -1;/*表示该点已经走过*/
}
}
front = front->next; /*对头向下走，直到结尾*/
}
if(flag == 0) /*若未收到成功信号，则表示迷宫走不通，报告不通。*/
puts("fail！");
}
void Print(Point *head) /*打印行进路径*/
{
Point *r;
r = head;
while(r->pre != NULL)
{
printf("(%d,%d)-> ", r->x, r->y);
r = r->pre;
}
printf("(%d,%d)\n", r->x, r->y);
}
Point *Change(void) //原队列中队尾元素表示出口坐标，打印出来的路径图是反的，
{
Point *p, *r, *s; //故将原路径复制到新队列中，对调指针方向，以便打印顺序路径图，
p = rear;
s = (Point *)malloc(sizeof(Point));
if(!s)
{
puts("出错了！");
getchar();
exit(OVERFLOW);
}
s->x = p->x;
s->y = p->y;
s->pre = NULL;
s->next = NULL;
r = s;
p = p->pre;
while(p)
{
s = (Point *)malloc(sizeof(Point));
if(!s)
{
puts("出错了！");
getchar();
exit(OVERFLOW);
}
s->x = p->x;
s->y = p->y;
s->pre = r;
s->next = NULL;
r->next = s;
r = s;
p = p->pre;
}
return r; /*返回复制的新队列，以便打印*/
}
void Free(void)
{
Point *r;
while(head)
{
r = head;
head = head->next;
free(r);
}
}
void Store(Point *head)
{
int i=0, flag=1;
while(flag)
{
if(head->pre != NULL)
{
a[row][i++] = '(';
a[row][i++] = (char)(head->x + 48);
a[row][i++] = ',';
a[row][i++] = (char)(head->y + 48);
a[row][i++] = ')';
a[row][i++] = '-';
a[row][i++] = '>';
a[row][i++] = ' ';
head = head->pre;
}
else
flag = 0;
}
a[row][i++] = '(';
a[row][i++] = (char)(head->x + 48);
a[row][i++] = ',';
a[row][i++] = (char)(head->y + 48);
a[row][i++] = ')';
a[row][i++] = '\0';
row++;
}
void Pai_Xu()
{
int i, j, min;
char p[200];
for(i=0; i<row-1; i++)
{
min = i;
for(j=i+1; j<row; j++)
if(strlen(a[min]) > strlen(a[j]) )
min = j;
if(min != i)
{
strcpy(p, a[i]);
strcpy(a[i], a[min]);
strcpy(a[min], p);
}
}
}
void Xiao_Chu()
{
int i, j;
char p[200]="fail";
for(i=0; i<row-1; i++)
for(j=i+1; j<row; j++)
if(strcmp(a[i], a[j]) == 0)
strcpy(a[j], p);
}
void Print_Total()
{
int i;
puts("\nthe total root:");
for(i=0; i<row-1; i++)
if(strcmp(a[i], "fail") != 0)
puts(a[i]);
}
正文
迷宫的算法2005-04-24 22:17:00
【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/goal00001111/705.html
阅读(3505) | 评论(0)
版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！
评论