经常会有类似的题目，如迷宫问题，在一个矩阵图中给定出发点和目标点，每次只能上下左右移动，求到目标点的最短走法，或者说是一共有多少种走法。

思路其实很简单，深搜、广搜。相对比较而言，广度优先搜索更加实用于求最短的走法（步数）

在矩阵图中的广搜需要注意一下几点.

1、确定每步的走法：不同题的走法可能不同，每次搜索时将走法保存在数组中。

2、确定初始状态 往往注意刚开始得起点（i，j）必须把MAP(i,j）改变为 -1（或者其他的），栈中第一个元素即为初始状态

3、保存状态。这点很重要。需要用数组或者其他的方法保存当前情况是否之前已经搜索过。如果没有这一步，将会死循环。

4、判断可行性:其实通常可以用一个Judge（）函数【bool】来判断每步的走法是否合乎要求，如果满足要求，则加入队列。

先来看一下最基础的迷宫问题

:给定一个矩阵图 0表示可走 -1表示不可走

给定起始位置 fx fy

目标位置 ex,ey

每次可以往上下左右四个放下前进

求到达目标位置的最小步数，并输出该路径。

c++代码（复习的时候写的）

include

#include

#include

#include

#include

#include

#include

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 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"<\
}\
\
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 -1

2 1

8 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

再来看进阶版的广搜（其实所有的广搜都不难，主要是要保存状态%>_<%）

说道保存状态 ，可以这样子来。

由于一个queueq 里面只能存放数字 那么怎么才能用一个数字保存一个状态？

用一个标记 cnt 和一个状态数组 State[] State数组用结构体定义

Struct{

int 状态 1;

int 状态 2；

...

...

}State[];

这样就可以一个cnt对应一个状态了~【貌似这个在深搜里面更好用- -】

看这样一个题(NOIP2013 Day2）

很明显，如果这道题不会（这道题正解方法真不不说了，HZX大神写了一天都没有写出来- -)

那么可以采用广搜 ：

因为空格子可以自由移动， 平且棋盘上除了起始点和空格格两个特殊的点之外，其他都是确定的，所以说状态唯一

用 vis[a][b][c][d]保存状态 分别是 空格子坐标 起始点坐标

在深搜空格的时候，（很明显这毫无次序，毫无章法，而且浪费很多时间，没有剪枝。。）

如果空格的路径走到了起始点，那么此时起始点的位置就必须要改变！每次搜的时候写一个判断就好了。

至于其他的的确不算特变难。注意每次询问的时候需要清零- -

c++代码

#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
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<int>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("0n"); 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("%dn",node[cnt].step); return ;} //判断目的 
            }
        }
    }
    printf("-1n");
    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;
}

好了，大概就是这样。必须要熟练掌握，关键时刻可以骗分- -
原文链接: https://www.cnblogs.com/ffhy/p/5664984.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍