博客

穷举法迷宫求解简单实现，主要是锻炼队列及链表的使用，直接上代码：

//
//  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;
}

最后上个图：