题解 P2385 【青铜莲花池】

· · 题解

标准的搜索题（就比如什么迷宫之类的），所以适合用来练广搜或深搜的熟练度。
我更倾向于用广搜来写（因为深搜更好写嘛，而且比如单词接龙这些题目只能用深搜写，到时候再练）。
广搜的思想，就是只处理“在手边上的事”；而深搜是“一条道走到黑”；具体来说，对一个状态（比如在迷宫中的位置），我们需要做四件事：
（1）检验是否处理完了整个事件（比如走到了出口），
以及（2and3）扩展（就是接下来能往那些方向走），
并（4）标记本状态为“已访问”，防止掉头回到这个状态。
广搜是扩展完再进入下一层，深搜是对一个状态扩展出的状态再扩展，尽可能"深"地搜索一张图。
那么，广搜如何实现呢？
我建议使用STL里的队列 (queue)(queue) 容器。
想象你每一个扩展到的结点去排队，等待处理；排到的结点做那四件事，扩展出的新结点再去排队，直到找到目标为止。
在你的头文件里加上#include<queue>
并在“using namespace std;”后加上“queue<int>q;”
来使用queue；

queue的常用操作：

q.push() :让结点去排队
q.front() :排最前面的结点。
q.pop() :处理完毕，最前面的结点离开。
q.empty() :队列里是否还有结点（有则为true）。

经常你能看到诸如pair<int,int>以及q.push(make_pair(x,y))之类的东西，那是因为系统自带的queue只能处理一个东西，如果你想把两个东西放进去就只有让它们成为“一对”，这就用到了pair。
某些情况下，我们可以用vis数组储存步数来减小空间复杂度（比如本题）。
代码见下： 

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=35;
int n,a,b,m,p,steps;
string s="suzhidiaocha";    //虽然本题均可到达，但还是防止万一
int maps[MAXN][MAXN];       //存图
int vis[MAXN][MAXN];        //存步数
void bfs(int sx,int sy,int fx,int fy){
    queue <pair<int ,int> >q;
    int dx[]={a,b,-a,-b,a,b,-a,-b};     //八个方向
    int dy[]={b,a,b,a,-b,-a,-b,-a};
    q.push(make_pair(sx,sy));           //基本上这就是模板了
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        if(x==fx&&y==fy){               //到终点就输出终点的步数，返回主程序
            cout<<vis[fx][fy]<<endl;
            return ;
        }
        q.pop();
        for(int z=0;z<=7;z++){
            int nx=x+dx[z];
            int ny=y+dy[z];
            if(nx<=m&&ny<=n&&nx>=1&&ny>=1&&!vis[nx][ny]&&maps[nx][ny]==1){                              //走得通
                vis[nx][ny]=vis[x][y]+1;    //存步数
                q.push(make_pair(nx,ny));   //  去排队
            }
        }
    }
    cout<<s<<endl;      //假如队空了也没找到，就是到不了
    return ;
}
int main(){
    int sx,sy,fx,fy;
    cin>>m>>n>>a>>b;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>maps[i][j];
            if(maps[i][j]==3){      //  找起始点
                sx=i;               //标记
                sy=j;
                maps[i][j]=1;
            }
            if(maps[i][j]==4){      //终点
                fx=i;
                fy=j;
                maps[i][j]=1;
            }
        }
    }

    bfs(sx,sy,fx,fy);

    return 0;           结束
}