穷举法迷宫求解简单实现,主要是锻炼队列及链表的使用,直接上代码:
//
// 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;
}
最后上个图:
分享到:
相关推荐
使用穷举法编写的C++迷宫解法。使用了数组操作模拟栈的操作。
本人亲手所写,绝对通俗易懂,数据结构so easy!!!
迷宫求解一般采用“穷举法”,逐一沿顺时针方向查找相邻块(一共四块-东(右)、南(下),西(左)、北(上))是否可通,即该相邻块既是通道块,且不在当前路径上。用一个栈来记录已走过的路径栈是限定仅在表尾(top)进行...
C语言使用队列和栈实现自动生成和求解迷宫
这是一款迷宫趣味游戏,能够自己生成地图,能够自动求解,当然也可以自己在迷宫中探索。只要机器上配置了java,就能运行。
数据结构C语言课程设计报告! 关于使用穷举法求解的,用链栈作为存储结构。该资源只是提供课程设计报告,并不提供源程序。作为一个写作模板提供。
数据结构C语言以链栈为存储结构的穷举法求解的迷宫,可以自动生成迷宫,可以自动生成有通路的迷宫,声称自动有通路的迷宫算法单一,以while死循环来生成,所以速度较慢,耐心等待。该资源为本人自己写的课程设计作业...
1.3 递推算法 1.4 枚举(穷举)算法 1.5 递归算法 1.6 分治算法 1.7 贪婪算法 ...4.8 合并排序法 5.3 二叉排序树 5.4 索引查找 6.6 矩阵的运算 7.1 约瑟夫环7.6 停车场管理 7.7 迷宫求解 7.8 LZW压缩的实现 8.3 魔术方阵
1.3 递推算法 1.4 枚举(穷举)算法 1.5 递归算法 1.6 分治算法 1.7 贪婪算法 ...4.8 合并排序法 5.3 二叉排序树 5.4 索引查找 6.6 矩阵的运算 7.1 约瑟夫环7.6 停车场管理 7.7 迷宫求解 7.8 LZW压缩的实现 8.3 魔术方阵
动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解。 动态规划的逆向思维法是指从问题目标状态出发倒退回初始状态或边界状态的...