穷举法迷宫求解简单实现（C）
穷举法迷宫求解简单实现，主要是锻炼队列及链表的使用，直接上代码：
//// main.c// migong//// Created by mac on 12-8-13.// Copyright 2012年 __MyCompanyName__. All rights reserved.//#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct{int x;int y;}DATA;typedef struct node{DATA data;struct node *next;}ListNode;typedef struct {int x;int y;int pre;}TP;TP qu[100];//队列int f,r;//迷宫数组，外面一圈1主要用于防止越界用int a[6][7]={ {1,1,1,1,1,1,1}, {1,0,1,1,1,0,1}, {1,1,0,1,0,1,1}, {1,0,1,0,0,1,1}, {1,0,1,1,1,0,1}, {1,1,1,1,1,1,1} }; //八个方向，上下左右，左上左下，右上右下int mg[8][2]={{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1}};//路径打印函数void print(int f,int m2,int n2){ListNode *h,*q,*p;int s,pr;s=f;h=(ListNode *)malloc(sizeof(ListNode));//链表头h->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->data.x=m2;q->data.y=n2;q->next=h->next;h->next=q; q=(ListNode *)malloc(sizeof(ListNode));q->data.x=qu[s].x;q->data.y=qu[s].y;q->next=h->next;h->next=q; pr=qu[s].pre; while(pr!=0){q=(ListNode *)malloc(sizeof(ListNode));q->data.x=qu[pr].x;q->data.y=qu[pr].y;q->next=h->next;h->next=q;pr=qu[pr].pre;}p=h->next;printf("(%d,%d)",p->data.x,p->data.y);p=p->next;while(p!=NULL){printf("--(%d,%d)",p->data.x,p->data.y);//打印链表p=p->next;}}//迷宫求解void MazePath(int m1,int n1,int m2,int n2){TP k;int p,q,v;f=r=0;k.x=m1;k.y=n1;k.pre=0;r++;qu[r]=k;a[m1][n2]=2;while(f<r)//队列不为空{f++;k=qu[f];for(v=0;v<8;v++)//八个方向穷举{p=k.x+mg[v][0];q=k.y+mg[v][1];if(a[p][q]==0){if(p==m2&&q==n2){print(f,m2,n2);return ;}r++;qu[r].x=p;qu[r].y=q;qu[r].pre=f;a[p][q]=2;}}}}int main (int argc, const char * argv[]){int i,j;printf("迷宫图:\n");puts("---------------------");for(i=0;i<6;i++){for(j=0;j<7;j++)printf(" %d ",a[i][j]);printf("\n");}puts("---------------------");printf("行走路径如下:\n");MazePath(1,1,4,5);printf("\n");return 0;}最后上个图：
