深度优先搜索.txt

图的搜索算法——包含深度优先搜索和广度优先搜索

　　#include <iostream.h>
　　#include <memory.h>
　　#define SX 11　// 宽
　　#define SY 10　// 长
　　int dx[4]={0,0,-1,1};　// 四种移动方向对x和y坐标的影响
　　int dy[4]={-1,1,0,0};
　　char Block[SY][SX] =　 // 障碍表
　　{{ 1,1,1,1,1,1,1,1,1,1,1 },
　　 { 1,0,1,0,1,0,0,0,0,0,1 },
　　 { 1,0,1,0,0,0,1,0,1,1,1 },
　　 { 1,0,0,0,1,0,1,0,0,0,1 },
　　 { 1,0,1,1,0,0,1,0,0,1,1 },
　　 { 1,0,1,0,1,1,0,1,0,0,1 },
　　 { 1,0,0,0,0,0,0,0,1,0,1 },
　　 { 1,0,1,0,1,0,1,0,1,0,1 },
　　 { 1,0,0,1,0,0,1,0,1,0,1 },
　　 { 1,1,1,1,1,1,1,1,1,1,1 }};
　　int MaxAct=4;　　　　　　// 移动方向总数
　　char Table[SY][SX];　　　// 已到过标记
　　int Level=-1;　　　　　　// 第几步
　　int LevelComplete=0; 　　// 这一步的搜索是否完成
　　int AllComplete=0;　 　　// 全部搜索是否完成
　　char Act[1000];　　　　　// 每一步的移动方向，搜索1000步，够了吧？
　　int x=1,y=1;　　　　 　　// 现在的x和y坐标
　　int TargetX=9,TargetY=8; // 目标x和y坐标
　　void Test( );
　　void Back( );
　　int ActOK( );
　　void main( )
　　{
　　　　memset(Act,0,sizeof(Act));　// 清零
　　　　memset(Table,0,sizeof(Table));
　　　　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--;　　　　　　　　// 回上一层
　　}
　　输出结果中1代表上，2代表下，3代表左，4代表右。