经常会有类似的题目，如迷宫问题，在一个矩阵图中给定出发点和目标点，每次只能上下左右移动，求到目标点的最短走法，或者说是一共有多少种走法。
思路其实很简单，深搜、广搜。相对比较而言，广度优先搜索更加实用于求最短的走法（步数）
在矩阵图中的广搜需要注意一下几点.
1、确定每步的走法：不同题的走法可能不同，每次搜索时将走法保存在数组中。
2、确定初始状态 往往注意刚开始得起点（i，j）必须把MAP(i,j）改变为 -1（或者其他的），栈中第一个元素即为初始状态
3、保存状态。这点很重要。需要用数组或者其他的方法保存当前情况是否之前已经搜索过。如果没有这一步，将会死循环。
4、判断可行性:其实通常可以用一个Judge（）函数【bool】来判断每步的走法是否合乎要求，如果满足要求，则加入队列。
先来看一下最基础的迷宫问题
:给定一个矩阵图 0表示可走 -1表示不可走
给定起始位置 fx fy
目标位置 ex,ey
每次可以往上下左右四个放下前进
求到达目标位置的最小步数，并输出该路径。
c++代码（复习的时候写的）
#include<string>
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<queue>#include<stack>using namespace std;int MAP[101][101],m,n,fx,fy,tx,ty,ex,ey,flag;int a[2][4]={ {0,0,1,-1},{1,-1,0,0}}; //第1步：路径走法 queue<int> q;struct Point{ int x; int y; int step; int prep;//前驱 }team[1000001];bool Judge(int x,int y){ if(x<=0||x>m) return false; if(y<=0||y>n) return false; if(MAP[x][y]==-1) return false; return true; }void print(int cnt){while(team[cnt].x!=fx||team[cnt].y!=fy)
{ cout<<team[cnt].x<<' '<<team[cnt].y<<endl; cnt=team[cnt].prep; } cout<<fx<<' '<<fy<<endl;}void BFS(){ MAP[fx][fy]=-1; //注意起点必须设为-1 int cnt=0; q.push(++cnt); team[1].x=fx;team[1].y=fy;team[1].step=0; //第2步，确定初始状态 while(!q.empty()) { int now=q.front(); q.pop();//取出栈首元素，出栈 for (int i=0;i<=3;i++) { int tx=team[now].x+a[0][i]; int ty=team[now].y+a[1][i]; int t_step=team[now].step; if(Judge(tx,ty))//判断是否可以走 //第4步：判断可行性，可在Judge函数中单独判断 { //cout<<tx<<' '<<ty<<endl; MAP[tx][ty]=-1; //第3步 保存状态 （迷宫问题保存状态超级简单- -） q.push(++cnt); team[cnt].x=tx;team[cnt].y=ty; team[cnt].step=t_step+1;team[cnt].prep=now; if(tx==ex&&ty==ey) {flag=1;print(cnt);break;} //到达目的 } } } if(flag==0) cout<<"N W"<<endl;}int main(){ cin>>m>>n; for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) cin>>MAP[i][j]; cin>>fx>>fy; cin>>ex>>ey; BFS(); return 0; }样例输入：
8 5
-1 -1 -1 -1 -1 0 0 0 0 -1-1 -1 -1 0 -1-1 0 0 0 -1-1 0 0 -1 -1-1 0 0 0 -1-1 -1 -1 0 -1-1 0 0 0 -12 18 4样例输出(貌似我是倒着输出的- -||）
2 1
2 2
2 3
2 4
3 4
4 4
4 3
5 3
6 3
6 4
7 4
8 4
再来看进阶版的广搜（其实所有的广搜都不难，主要是要保存状态%>_<%）
说道保存状态 ，可以这样子来。
由于一个queue<int>q 里面只能存放数字 那么怎么才能用一个数字保存一个状态？
用一个标记 cnt 和一个状态数组 State[] State数组用结构体定义
Struct{
int 状态 1;
int 状态 2；
...
...
}State[];
这样就可以一个cnt对应一个状态了~【貌似这个在深搜里面更好用- -】
看这样一个题(NOIP2013 Day2）
很明显，如果这道题不会（这道题正解方法真不不说了，HZX大神写了一天都没有写出来- -)
那么可以采用广搜 ：
因为空格子可以自由移动， 平且棋盘上除了起始点和空格格两个特殊的点之外，其他都是确定的，所以说状态唯一
用 vis[a][b][c][d]保存状态 分别是 空格子坐标 起始点坐标
在深搜空格的时候，（很明显这毫无次序，毫无章法，而且浪费很多时间，没有剪枝。。）
如果空格的路径走到了起始点，那么此时起始点的位置就必须要改变！每次搜的时候写一个判断就好了。
至于其他的的确不算特变难。注意每次询问的时候需要清零- -
c++代码
#include#include #include #include #include #include #include using namespace std; const int maxn=30+2,MAX=810000+5; const int move[2][4]={ { 0,0,1,-1},{-1,1,0,0}}; int n,m,q,MAP[maxn][maxn]; bool vis[maxn][maxn][maxn][maxn]; struct NODE { int bx,by,lx,ly,step; }node[MAX]; bool judge(int a,int b,int c,int d) { if (!MAP[c][d]||c<1||d<1||c>n||d>m) return false; if (vis[a][b][c][d]) return false; vis[a][b][c][d]=true; return true; } void bfs() { queue q; memset(vis,0,sizeof(vis)); int ex,ey,cnt=0; scanf("%d %d %d %d %d %d",&node[1].bx,&node[1].by,&node[1].lx,&node[1].ly,&ex,&ey); if (node[1].lx==ex&&node[1].ly==ey){printf("0\n"); return ;} vis[node[1].lx][node[1].ly][node[1].bx][node[1].by]=true; q.push(++cnt); node[cnt].step=0; while(!q.empty()) { int now=q.front(); q.pop(); //取出一个栈顶元素 for (int i=0;i<=3;i++) { int tlx=node[now].lx,tly=node[now].ly; int tbx=node[now].bx+move[0][i],tby=node[now].by+move[1][i]; if (tlx==tbx&&tly==tby){tlx=node[now].bx; tly=node[now].by;} //如果白点移动到出发点 if (judge(tlx,tly,tbx,tby)) //判断新加的点是否符合要求 则出发点位置更新为白点 { q.push(++cnt); //入栈 node[cnt].bx=tbx; node[cnt].by=tby; //更新状态 node[cnt].lx=tlx; node[cnt].ly=tly; node[cnt].step=node[now].step+1; if (tlx==ex&&tly==ey) {printf("%d\n",node[cnt].step); return ;} //判断目的 } } } printf("-1\n"); return ; } int main() { freopen("puzzle.in","r",stdin); freopen("puzzle.out","w",stdout); cin>>n>>m>>q; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&MAP[i][j]); for (int i=1;i<=q;i++) bfs(); return 0; }
好了，大概就是这样。必须要熟练掌握，关键时刻可以骗分- -