深度搜索算法C语言实现--以走迷宫为例

2016-12-29 19:33:03来源:CSDN作者:Deep_l_zh人点击

第七城市

深度搜索算法是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

dfs.h
#ifndef __DFS_H_  #define __DFS_H_  #define u32 unsigned int#define u16 unsigned short#define s32 int#define TRUE		1#define FALSE		0#define ROW		5#define COLUMN	5#define ROAD	0#define WALL	1#define PASS	2typedef struct{	u32 x;	u32 y;}loc_in_maze;void print_maze(void);void  print_path(void);void dfs_maze(u32 loc_x,u32 loc_y);#endif


dfs.c
#include <stdio.h>#include <string.h>#include <stdlib.h>#include <memory.h>#include "dfs.h"loc_in_maze path[25];u32 path_flag = 0;const s32 d_x[4]={0,1,0,-1};const s32 d_y[4]={1,0,-1,0};u32 maze[ROW][COLUMN]={	ROAD,WALL,ROAD,ROAD,ROAD,	ROAD,WALL,ROAD,WALL,ROAD,	ROAD,ROAD,ROAD,ROAD,ROAD,	ROAD,WALL,WALL,WALL,ROAD,	ROAD,ROAD,ROAD,WALL,ROAD	};void print_maze(void){	u32 i,j;	for(i=0;i<ROW;i++)	{		for(j=0;j<COLUMN;j++)		{			printf("%d",maze[i][j]);		}		printf("/n");	}	printf("******/n");}void  print_path(void){	u32 i;	printf("(0,0)");	for(i=0;i<path_flag;i++)	{		printf("->(%d,%d)",path[i].x,path[i].y);	}	printf("/n");}void dfs_maze(u32 loc_x,u32 loc_y){	int k;	for(k=0;k<4;k++)	{		if(loc_x+d_x[k]>=0&&loc_x+d_x[k]<5&&loc_y+d_y[k]>=0&&loc_y+d_y[k]<5&&maze[loc_x+d_x[k]][loc_y+d_y[k]]==0)		{			maze[loc_x+d_x[k]][loc_y+d_y[k]]=2;			path[path_flag].x=loc_x+d_x[k];			path[path_flag].y=loc_y+d_y[k];			path_flag++;			print_maze();			if(loc_x+d_x[k]==4&&loc_y+d_y[k]==4)			{				print_path();				getch();				exit(0);			}			else			{				dfs_maze(loc_x+d_x[k],loc_y+d_y[k]);			}			maze[loc_x+d_x[k]][loc_y+d_y[k]]=0;			path[path_flag].x=0;			path[path_flag].y=0;			path_flag--;		}	}}int main(void){	dfs_maze(0,0);	getch();	return 0;}



第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台