广度优先搜索.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 AllComplete=0;　// 全部完成标志
　　int LevelNow=1,　　 // 搜索到第几层
　　　　Act,　　　　　　// 现在的移动方向
　　　　ActBefore,　　　// 现在的节点的父节点
　　　　MaxAct=4,　　　 // 移动方向总数
　　　　ActNow,　　　　 // 现在的节点
　　　　tx,ty;　　　　　// 当前坐标
　　int LevelFoot[200], // 每一层最后的节点
　　　　ActHead[3000];　// 每一个节点的父节点
　　char AllAct[3000];　// 每一个节点的移动方向
　　char ActX[3000],
　　　　 ActY[3000];　　// 按节点移动后的坐标
　　char Table[SY][SX]; // 已到过标记
　　char TargetX=9,
　　　　 TargetY=8;　　 // 目标点
　　int ActOK( );
　　int Test( );
　　int ActOK( )
　　{
　　　　tx=ActX[ActBefore]+dx[Act-1];　// 将到点的x坐标
　　　　ty=ActY[ActBefore]+dy[Act-1];　// 将到点的y坐标
　　　　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;
　　　　return 1;
　　}
　　int Test( )
　　{
　　　　if ((tx==TargetX)&&(ty==TargetY))　// 已到目标
　　　　{
　　　　　　int act=ActNow;
　　　　　　while (act!=0)
　　　　　　{
　　　　　　　　cout<<(int)AllAct[act];　// 一步步向前推出所有移动方向
　　　　　　　　act=ActHead[act];　　　　// 所以输出倒了过来
　　　　　　}
　　　　　　return 1;
　　　　}
　　　　return 0;
　　}
　　void main()
　　{
　　　　memset(Table,0,sizeof(Table));
　　　　memset(LevelFoot,0,sizeof(LevelFoot));
　　　　memset(ActHead,0,sizeof(ActHead));
　　　　memset(AllAct,0,sizeof(AllAct));
　　　　memset(ActX,0,sizeof(ActX));
　　　　memset(ActY,0,sizeof(ActY));　// 变量清零
　　　　LevelNow=1;
　　　　LevelFoot[1]=0;
　　　　LevelFoot[0]=-1;
　　　　ActX[0]=1;
　　　　ActY[0]=1;
　　　　while (!AllComplete)
　　　　{
　　　　　　LevelNow++;　// 开始搜索下一层
　　　　　　LevelFoot[LevelNow]=LevelFoot[LevelNow-1];
　　　　　　// 新一层的尾节点先设为与上一层相同
　　　　　　for (ActBefore=LevelFoot[LevelNow-2]+1;
　　　　　　　　ActBefore<=LevelFoot[LevelNow-1];
　　　　　　　　ActBefore++)　// 对上一层所有节点扩展
　　　　　　{
　　　　　　　　for (Act=1;Act<=MaxAct;Act++)　// 尝试所有方向
　　　　　　　　{
　　　　　　　　　　if ((ActOK( )) && (!AllComplete))　// 操作可行？
　　　　　　　　　　{
　　　　　　　　　　　　LevelFoot[LevelNow]++;　　　 // 移动尾指针准备加入新
节点
　　　　　　　　　　　　ActNow=LevelFoot[LevelNow];　// 找到加入新节点位置
　　　　　　　　　　　　ActHead[ActNow]=ActBefore;　 // 置头指针
　　　　　　　　　　　　AllAct[ActNow]=Act;　　　　　// 加入新节点
　　　　　　　　　　　　ActX[ActNow]=tx;
　　　　　　　　　　　　ActY[ActNow]=ty;　　　　　　 // 存储移动后位置
　　　　　　　　　　　　Table[ty][tx]=1;　　　　　　 // 做已到过标记
　　　　　　　　　　　　if (Test( )) AllComplete=1;　// 完成？
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}
　　　　}
　　}