/*
* =====================================================================================
*
* Filename: maze.c
*
* Description:
*
* Version: 1.0
* Created: 2011年12月09日 21时33分32秒
* Revision: none
* Compiler: gcc
*
* Author: YOUR NAME (),
* Company:
*
* =====================================================================================
*/
#include <stdio.h>
#include <stdlib.h>
int b[5][15]= {0};
int cnt_path = 0;
int min = 65535;
/*stack*/
struct stack_node
{
int x;
int y;
struct stack_node *next_ptr;
};
void push(struct stack_node **top_ptr, int x, int y)
{
struct stack_node *new_ptr;
new_ptr = malloc(sizeof(struct stack_node));
if (new_ptr != NULL)
{
new_ptr->x = x;
new_ptr->y = y;
new_ptr->next_ptr = *top_ptr;
*top_ptr = new_ptr;
}
}
void pop(struct stack_node** top_ptr)
{
struct stack_node* temp_ptr;
temp_ptr = *top_ptr;
*top_ptr = (*top_ptr)->next_ptr;
free(temp_ptr);
}
void print_stack(struct stack_node* current_ptr)
{
if(current_ptr == NULL)
{
printf("the stack is empty.\n");
}
else
{
while(current_ptr != NULL)
{
printf("(%d,%d)\n", current_ptr->x, current_ptr->y);
current_ptr = current_ptr->next_ptr;
}
printf("NULL\n ");
}
}
int is_empty(struct stack_node * top_ptr)
{
return top_ptr == NULL;
}
int find(int a[5][15], int i, int j, int n, int m, struct stack_node *stack_ptr)
{
b[i][j] = 1;
cnt_path++;
push(&stack_ptr, i+1, j+1);
if (a[i][j] == 2)
{
print_stack(stack_ptr);
printf("%d\n", cnt_path);
cnt_path--;
return 0;
}
if (j + 1 < m)//右
{
if (0 != a[i][j+1] && 0 == b[i][j+1] )
{
find(a, i, j+1, n, m,stack_ptr);
}
}
if (i + 1 < n)//下
{
if (0 != a[i+1][j] && 0 == b[i+1][j])
{
find(a, i+1, j, n, m,stack_ptr);
}
}
if (j - 1 >= 0 )//左
{
if (0 != a[i][j-1] && 0 == b[i][j-1])
{
find(a, i, j-1, n, m,stack_ptr);
}
}
if (i - 1 >= 0)//向上
{
if (0 != a[i-1][j] && 0 == b[i-1][j])
{
find(a, i-1, j, n, m,stack_ptr);
}
}
b[i][j] = 0;
cnt_path--;
pop(&stack_ptr);
}
int main()
{
int n,m;
n = 5;
m = 15; //exit 2 start 3
struct stack_node * stack_ptr = NULL;//在第第一次push的时候NULL会被复制到top_ptr->next_ptr中
int a[5][15] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
3,1,1,1,1,1,1,1,1,1,1,1,2,0,0,
0,0,1,0,0,1,0,0,0,0,0,0,1,1,0,
0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,2,0,0};
find(a, 1, 0, n, m, stack_ptr);//1,0代表出发的坐标,也就是3的坐标
}
- 浏览: 124901 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (341)
- Java (18)
- J2EE (0)
- Linux (81)
- VIM (22)
- windows (6)
- DB (11)
- Algorithm (57)
- Data structure (17)
- JS (5)
- C++ (65)
- HTML (6)
- Cloud (4)
- Eclipse (7)
- Python (42)
- Play (3)
- HTTP (1)
- awk (7)
- shell (20)
- Regular expression (5)
- NLP (33)
- ML (38)
- DM (43)
- Probabilistic (6)
- Crawler (14)
- matlab (1)
- perl (4)
- Design pattern (1)
- IO[File] (2)
- Deep Learning (1)
发表评论
-
正向插入排序
2011-09-28 21:51 310/* * ========================== ... -
归并排序
2011-10-07 23:22 247/* *========================= ... -
二叉排序树
2011-10-31 15:46 242#include <stdio.h> #inclu ... -
动态栈
2011-10-31 15:47 300/* * ========================== ... -
struct in_addr
2011-11-03 17:29 303struct in_addr addr_ip; struct ... -
UNIX创建临时文件
2011-11-04 13:26 289/* * ========================= ... -
UNIX目录扫描
2011-11-04 17:09 307/* * ========================== ... -
8皇后(按列递归)
2011-12-10 17:55 285/* * ========================== ... -
epoll(精髓)
2011-12-23 09:47 246epoll - I/O event notification ... -
Linux Epoll介绍和程序实例
2011-12-23 09:47 2461. Epoll是何方神圣? Epoll可是当前在Linu ... -
Beli Makfile for linux
2012-04-25 13:12 323.SUFFIXES: .c .u CC= gcc # CFLA ... -
gsl eclipse
2012-04-25 14:27 4641 我的gsl安装路径:D:/GnuWin32 1 ... -
动态规划
2012-06-15 13:39 299前言 和分治法一样,动态规划(dynamic progra ... -
01背包图解
2012-06-15 17:06 32101背包问题描述:一个 ... -
动态规划 最短路径
2012-06-18 22:35 449动态规划求有向无环图的最短路径 问题描述如下 ... -
Linux下获取毫秒级时间差
2012-08-22 19:46 525Linux下获取毫秒级时间差 使用Linux的ge ... -
CPU Sin
2012-08-22 21:12 3221 #include <iostream> ... -
正文提取
2012-10-25 11:36 375目前互联网上公布出来的正文提取算法,大家可以综合比较下,一起 ... -
C++ 补全插件
2012-10-30 20:16 294config vim + clang complete wi ... -
c++ clang_complete
2012-12-17 17:01 306前一段时间发现了clang complete,发现效果 ...
相关推荐
然后依次再从这些点出发,再记下所有一步能到达的坐标点,…,依此类推,直到到达迷宫的出口点(m,n)为止,然后从出口点沿搜索路径回溯直至入口。这样就找到了一条迷宫的最短路径,否则迷宫无路径。
演示深度搜索找迷宫出口的过程。运用栈的知识,MFC的展示更为形象
在一个指定的迷宫里,出口和入口指定,找到一条路出去
设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 实现要求: ⑴ 实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式...
利用广度优先探索算法,实现迷宫出口探索,数据结构
题目:假设迷宫由m行n列构成,有一个入口和一个出口,入口坐标为(1,1),出口坐标为(m,n),试找出一条从入口通往出口的最短路径。设计算法并编程输出一条通过迷宫的最短路径或报告一个“无法通过”的信息。 要求:...
设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 [基本要求] 首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫问题的非递归算法。求得的通路以三元组(i,j,d)...
简单的用链栈实现找出一条迷宫出口
设计并实现了一个指定迷宫入口和出口、搜索迷宫走出路径的程序。
迷宫是一个二维矩阵,其中1为墙,0为路,3为入口,4为出口.要求从入口开始,从出口结束,按照 下,左,上,右 的顺序来搜索路径. 输入: 迷宫宽度w 迷宫高度h 迷宫第一行 迷宫第二行 ... 迷宫第h 行 输出: 入口横坐标1 入口...
有一个N*M的格子迷宫,1代表该格子为墙,不能通过,0代表可以通过,另外,在迷宫中有一些传送门,走到传送门的入口即会自动被传送到传送门的出口(一次传送算1步)。人在迷宫中可以尝试上下左右四个方向移动。现在...
心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫,迷宫中设置很多隔壁,对前进方向形成了多处障碍,心理学家在迷宫的唯一出口放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口老鼠能够记住已经走过的路,...
实现基于基础搜索算法和 Deep QLearning 算法的机器人,使机器人自动走到迷宫的出口。 使用 Python 语言。 使用基础搜索算法完成机器人走迷宫。 使用 Deep QLearning 算法完成机器人走迷宫。 使用 Maze(maze_size=...
迷宫的规格(即行数与列数),状态设置(即各方格能否通行的状态),以及入口和出口的位置,均应由输入随机确定。 2。求得的最短路径,应该以从入口到出口的路径上的各个方格的坐标的线性序列输出。当无通路时,应该...
任务:以一个m n的长方阵表示迷宫 0和1分别表示迷宫中的通路和障碍 设计一个程序 对任意设定的迷宫 求出一条从入口到出口的通路 或得出没有通路的结论...要求:首先实现一个栈类型 然后编写一个求解迷宫的非递归 [更多]
迷宫求解是实验心理学中的一个经典问题,心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫,迷宫中设置很多隔壁,对前进方向形成了多处障碍,心理学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中...
设计一个可以调整大小的迷宫游戏,给定迷宫的...如果存在出口,程序能够显示行走的路径,并最终到达出口,并输出“成功走出迷宫”;如果不存在出口,程序也能够显示行走的过程,并最终回退到入口,并输出“回退到入口”
多怪物追踪随机通路迷宫 g键添加怪物 迷宫wasd控制,找到迷宫出口为胜
设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 (1) 根据二维数组,输出迷宫的图形。 (2) 探索迷宫的四个方向:RIGHT为向右,DOWN向下,LEFT向左,UP向上,输出从入口到...
盒子仅有一个出口,在出口处放置一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入口走到出口,而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线.....