搜索------（一）
迷宫问题：
寻找从入口到出口的最短路径
宽度优先搜素：（采用队列的方式）
思路：采用队列的方法，以入口为基准，凡是可通行的地方均入队列，以入队列的每一个元素为基准向四周的八个方向进行搜素，在搜素的过程中找到出口则采用回溯的方法将最短路径输出，每当一个元素向四周八个方向搜素完毕后，则将第一个元素出队列。
（八方向行走迷宫，0表示可行通路。）
实现代码：
#include <iostream>
#include <stdio.h>
#define m 5 /*行数*/
#define n 5 /*列数*/
#define MaxSize 100
using namespace std;int zx[9]={0,-1,-1,0,1,1,1,0,-1};
int zy[9]={0,0,1,1,1,0,-1,-1,-1};
int mg[m+2][n+2]={1,1,1,1,1,1,1,1,0,0,0,1,0,1,1,0,1,0,0,0,1,1,0,0,1,0,1,1,1,1,1,0,1,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1};
struct stype
{int x,y,pre;//pre表示前一步
}quenu[MaxSize];
void print_1(int real)
{int i,j;i=real;do{j=i;i=quenu[i].pre;quenu[j].pre=-1;}while(i!=0);printf("\n入口：");i=0;while(i<MaxSize){if(quenu[i].pre==-1){printf("(%d,%d)->",quenu[i].x,quenu[i].y);}i++;} printf("出口\n");
}
void sousu()
{int front,real,find=0,i,j,v,x,y;front =1;real=1;quenu[front].x=1;quenu[front].y=1;quenu[front].pre=0;mg[1][1]=-1;while(front<=real&&!find){x=quenu[front].x;y=quenu[front].y;for(v=1;v<=8;v++){i=x+zx[v];j=y+zy[v];if(mg[i][j]==0){real++;quenu[real].x=i;quenu[real].y=j;quenu[real].pre=front;mg[i][j]=-1;}if(i==m&&j==n){print_1(real);find=1;}}front++;}if(!find){printf("不存在路径/n");}
}
int main()
{sousu();getchar();
}
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#define N 1000
using namespace std;struct Map //第一步：构造每个元素位置 ，用数组命令后形成方格图。
{int x;int y;
}pre[N][N];
int map[N][N];
bool vist[N][N];
int a[4][2]={
{-1,0},{0,-1},{1,0},{0,1}};
void printway(int x,int y)
{int i,j,k;if(x==0&&y==0){printf("%d%d\n",x+1,y+1);return;}printway(pre[x][y].x,pre[x][y].y);printf("%d%d\n",x+1,y+1);}
bool in(int x,int y)
{if(x<0||y<0||x>4||y>4){return false;}return true;
}
void bfs()
{int i,j,k;queue<Map>q; //第四步：构建队列 while(!q.empty()){q.pop();}vist[0][0]=true;Map cur;cur.x=0;cur.y=0;q.push(cur);while(!q.empty())//第五步：进行广度搜素，通路就入队列，每个元素四个方向判断完后就出队列 {cur=q.front();q.pop();for(i=0;i<4;i++){int x=cur.x+a[i][0];int y=cur.y+a[i][1];if(in(x,y)&&!vist[x][y]&&!map[x][y]){Map temp;vist[x][y]=true;temp.x=x;temp.y=y;q.push(temp);pre[x][y].x=cur.x;pre[x][y].y=cur.y;}if(x==4&&y==4){printway(4,4);}}}
}int main()
{int i,j;for(i=0;i<5;i++) // 第二步，输入0/1表示通路/不通路 {for(j=0;j<5;j++){cin>>map[i][j];}}memset(vist,false,sizeof(vist));// 使用时在文件头加上#include "string.h" 。bfs();
}
宽度优先搜素：
其思想采用的是栈，向下不断搜素，知道得到结果即可输出最短路径。