dfs.cpp

《游戏编程指南》配套代码 [涉及平台] VC++ [作者] void [文件大小] 1761KB [更新日期] 2005-10-26

/*
	例如，下面的地图(黑色的格子代表墙，其它格子都是可以行走的)
	如果要从左上角走到右下角，深度优先搜索的次序如下(A->Z->a->o)：
   	  g g g g g g g g g g g
   	  g Ａ g ａ g ｄ ｅ ｆ c c g
   	  g Ｂ g Ｚ ｂ ｃ g ｇ g g g
      g Ｃ Ｘ Ｙ g c g ｈ c c g
   	  g Ｄ g g c c g ｉ ｊ g g
   	  g Ｅ g Ｌ g g Ｔ g ｋ ｌ g
   	  g Ｆ Ｊ Ｋ Ｎ Ｏ Ｓ Ｕ g ｍ g
   	  g Ｇ g Ｍ g Ｐ g Ｖ g ｎ g
   	  g Ｈ Ｉ g Ｒ Ｑ g Ｗ g ｏ g
   	  g g g g g g g g g g g

图8.1

*/

//下面就是标准的深度优先搜索程序：
#include <iostream>
#include <memory>
using namespace std;

#define SX	10 //宽
#define SY	10 //长

int dx[4]={0,0,-1,1}; //四种移动方向对x和y坐标的影响
int dy[4]={-1,1,0,0};

char Block[SY][SX]= //障碍表
{{	0,1,0,0,0,0,0,0,0,0	},
{   0,1,1,0,1,1,1,0,0,0	},
{   0,0,0,0,0,0,0,0,0,0	},
{	1,1,1,0,1,0,0,0,1,0	},
{	0,1,0,0,1,0,1,1,1,0	},
{	0,1,0,0,1,1,1,1,1,0	},
{	0,0,0,1,1,0,0,0,1,0	},
{	0,1,0,0,0,0,1,0,1,0	},
{	0,1,1,1,0,1,1,0,1,1	},
{	0,0,0,0,0,0,1,0,0,0	}};

int		 MaxAct=4; //移动方向总数
char	 Table[SY][SX]={0}; //是否已到过
int		 Level=-1; //第几步
int		 LevelComplete=0; //这一步的搜索是否完成
int		 AllComplete=0; //全部搜索是否完成
char	 Act[1000]={0}; //每一步的移动方向，搜索1000步
int		 x=0,y=0; //现在的x和y坐标
int		 TargetX=9,TargetY=9; //目标x和y坐标
	
void	 Test( );
void	 Back( );
int		 ActOK( );
	
void main( )
{
	Table[y][x]=1; //做已到过标记
	while (!AllComplete) //是否全部搜索完
	{
		Level++;LevelComplete=0; //搜索下一步
			while (!LevelComplete)
		{
				Act[Level]++; //改变移动方向
		if (ActOK( )) //移动方向是否合理
			{
				Test( ); //测试是否已到目标
					LevelComplete=1; //该步搜索完成
		}
			else
			{
					if (Act[Level]>MaxAct) //已搜索完所有方向
						Back( ); //回上一步
			if (Level<0) //全部搜索完仍无结果
					LevelComplete=AllComplete=1; //退出
				}
		}
	}
}

void Test( )
{
		if ((x==TargetX)&&(y==TargetY)) //已到目标
	{
		for (int i=0;i<=Level;i++)
			cout<<(int)Act[i]; //输出结果
		LevelComplete=AllComplete=1; //完成搜索
	}
}

int ActOK( )
{
		int tx=x+dx[Act[Level]-1]; //将到点的x坐标
	int ty=y+dy[Act[Level]-1]; //将到点的y坐标
	if (Act[Level]>MaxAct) //方向错误？
			return 0;
	if ((tx>=SX)||(tx<0)) //x坐标出界？
		return 0;
	if ((ty>=SY)||(ty<0)) //y坐标出界？
		return 0;
	if (Table[ty][tx]==1) //已到过？
		return 0;
	if (Block[ty][tx]==1) //有障碍？
		return 0;
	x=tx;
	y=ty; //移动
	Table[y][x]=1; //做已到过标记
	return 1;
}


void Back( )
{
		x-=dx[Act[Level-1]-1];
	y-=dy[Act[Level-1]-1]; //退回原来的点
	Table[y][x]=0; //清除已到过标记
	Act[Level]=0; //清除方向
	Level--; //回上一层
}