高级搜索题集

题集转自以下链接：

https://blog.csdn.net/shahdza/article/details/7986044

---

 胜利大逃亡(续) HDU - 1429 

题意：就是二维地图，有障碍；重点有门，和钥匙（用于开门）。

理解：因为找钥匙，这个解答路径可能会走回头路。

思路：第一遍，因为有时间限制，并且20*20；所以简单bfs，然后MLimit了。感觉就是重复存储点在队列。

那么难点就在于判重了。因为走回头路，简单二维判重肯定不行。

回想和之前炮台那题，因为子弹的原因也是走回头路，所以判重数组多加了一个时间维度。

这题关键因素是钥匙，所以加一个钥匙拥有状态的判重，就ac了。（用2进制状态压缩，这里因为a-j，所以数组开个1024就够了。）

#include 
#include 
#include 
#include 

using namespace std;

int n,m,t;
char ditu[21][21];
bool vis[1025][21][21];
int Sx,Sy,Fx,Fy;

int xx[] = {0,0,1,-1};
int yy[] = {1,-1,0,0};

struct node{
    int x,y,step,k=0;
    node(int a,int b,int c,int d):x(a),y(b),step(c),k(d) {};
};


bool bfs(){
    memset(vis,false,sizeof vis);
    queue q;q.push(node(Sx,Sy,0,0));vis[0][Sx][Sy] = true;
    while(!q.empty()){
        node p = q.front();q.pop();
        for(int i=0;i<4;i++){
            int x = p.x+xx[i],y = p.y+yy[i];
            if(x<0||x>=n||y<0||y>=m||ditu[x][y]=='*'||p.step+1>=t) continue;
            int step = p.step + 1,k = p.k;
            if(ditu[x][y]>='A'&&ditu[x][y]<='Z'&&!(p.k&(1<'A'))) continue;
            if(ditu[x][y] == '^') {cout<return true;}
            if(ditu[x][y]>='a'&&ditu[x][y]<='z') k |= 1<<(ditu[x][y]-'a');
            if(vis[k][x][y]) continue;
            q.push(node(x,y,step,k));vis[k][x][y] = true;
        }
    }
    return false;
}

int main()
{
    while(cin>>n>>m>>t){
        for(int i=0;ifor(int j=0;j){
            char ch = getchar();while(ch==' '||ch=='\n') ch = getchar();
            ditu[i][j] = ch;
            if(ch=='^') Fx = i,Fy = j;
            else if(ch=='@') Sx = i,Sy = j;
        }

        if(!bfs()) puts("-1");
    }
    return 0;
}

---

 这题给我启发就是，判重作用在于剪枝，避免重复的入队操作。那么关键在于什么？关键在于点状态更新，并且取决于什么要素关键，炮台那题，因为子弹原因，时间是关键。这题因为门的原因，钥匙是关键。所以添加关键要素的判重数组是解题关键。

---

---

Key Task HDU - 1885 

题意与上题一样。但是地图大小和钥匙，门出口数量不同。

#include 
#include 
#include 
#include 
#include 

扩展思考：我这里想到如果钥匙并非永久产品而是一次性，那该怎么办？

我感觉难点可能在于不止走一次回头路。

我一开始能想到就是：像多重背包操作一样，将问题转化为0-1，多个相同门和钥匙，对应将他们分类成不同颜色。额，好像不行，因为你不清楚那个钥匙对应哪个门即为最优。。。。

那判重函数多加一维度，有什么颜色钥匙，并且多一个钥匙数量的维度。

---

 超级密码HDU - 1226 

算法：BFS

思路：BFS向下操作，*进制数+构成数 然后 对N求余 得到 的余数，因为是要正整数倍，所以当余数为0则为答案。

K1%N = K2%N；（K1*C+M）%N = （K2*C+M）%N ；所以余数可以作为判重点。相同余数不需要重复入队。

用数组记录答案长度，因为BFS是有层次性，所以超过500就可以判负了。

#include 
#include 
#include 
#include 
#include 
#include 

---

 Different DigitsHDU - 1664 

算法：数论+BFS

思路：感觉这题集出得挺不错，每道题总与上一道题有关联。这一题和上一题一样，也是求N的正整数倍。所以也是余数下手。

但是这题巧妙在于，最优解是，答案需尽量少不同数字构成且最小。

这里牵扯的数论就是：

 很好理解：求10进制的余数，（*10+1）MOD，因为只加一个数字的求余存在一个循环，存在0则为答案。余数相同，就互减得到答案，互减将余数减掉就是N的整数倍了。

所以一个整数一定存在一个正整数倍的数，且由0和1的数构成。

所以，两不同数字就构成本题答案；

那么这题剩下就是求一个最优最小解，即不同数字的数量相同求最小。

分两层，第一层只用一个数叠加求，得到答案就是最优。得不到去第二层，循环从不同两个数字组合求出答案。

#include 
#include 
#include 
#include 
#include 
#include 

 

---

 Pusher HDU - 2821 

算法：枚举+dfs（简单模拟）

题意：类似手机游戏，一副25*25的地图，有多个障碍物，障碍物由字母表示，a为一方块，b为内嵌的2方块，以此类推。

球体，要选取一个地方起步（这里我用全地图枚举），进行弹射必须有一个空格当空隙。

起步后，方向不变，直到撞到方块才停下，且推方块向后一步，方块数减一，剩余方块积累到后一步。后一步如果是地图外，则起步方块消失。

如果球飞出地图，则失败。

#include 
#include 
#include 
#include 
#include 
#include 

---

 Tempter of the Bone IIHDU - 2128 

算法：BFS/DFS

题意：就是给一个有障碍的地图，图上有炸弹推，经过就可以捡上，不过只能捡一次。炸弹可以炸墙，不过算一步。

判重就简单的3维，坐标加炸弹。

---

 BFS

这里我BFS，直接模拟，找到答案直接输出，然后wrong了。

后面看别人代码，得知原因，因为，我直接将炸开炸弹，与进入墙体两步，结合在一层进行模拟；

容易导致BFS跨步错误，就像之前做过的一道题，情侣被鬼追，G - Nightmare Ⅱ  HDU - 3085 。这题我在kuangbin题集做了解析。

这里类似2步走，第二步vis标记会导致其他第一步入队而出现答案错误，wrong。

这里我是看别人代码学的操作，将vis移到出队再加，然后答案，通过ans记录，并进行求最短剪枝。这里就相当于将vis标记放到下一层去判断，虽然会增加入队冗余，但是ans优化也减了一部分。

一开始码的时候不知道这样对不对？不管先试了再说。然后就AC了。

#include 
#include 
#include 
#include 
#include 
#include 

后面想验证一下，到底是不是炸弹并步走，才导致的wrong，我就尝试将炸弹和入墙分为两步，再不同层进行。结果也AC。所以之前wrong就是BFS跨步走问题。

#include 
#include 
#include 
#include 
#include 
#include 

---

 IDEA*  

这里我DFS模拟，我决策函数用哈夫曼函数。然后模拟与上面BFS无疑，重点这里DFS也需要一步步来,因为想求得即最优。

可能存在没有答案，所以limit需要上限，8*8 = 64，64-2 = 62；然后取7个空作9炸弹，剩下55个空都是墙，然而63>55,所以55个墙为最坏情况，63+55 = 108步。上限为108；

（这里最坏情况假设，每次拿最近的炸弹必须用完之前的，每细想其他细节，所以大概就估算）

#include 
#include 
#include 
#include 
#include 
#include 

---

 Ali and BabaHDU - 4101 

算法：BFS + 博弈判奇偶

难点：题目在于理解。因为博弈，两人都是以自己最优的思路操作。所以胜负关键点很重要。

胜负关键点在于，谁最后打开宝藏包围圈谁输。

题意：一副地图，只有一个宝藏，然后存在石头推（以数字表示，<100），然后每人每步可以打碎一个石头。然后走路不算操作数。

思路：第一步：先标记从宝藏出发能达到的0点（包括宝藏自身也要标记），因为到达这里就表示已经赢了；这里如果标记点，存在于边界，就表示Ali不用破碎石头就能拿宝藏，所以Ali Win；

　　　第二步：获取走到胜负关键点的总操作数。（胜负关键点就是谁可以走到那些上一步的标记点，因为谁都不想帮别人破最后的石头，所以就会选择破其他无关石头，所以要记录所有外围石头数即总操作数）；这里简单联想一下，就是这一步宝藏外围一定有一个石头包围圈即屏障，谁先打破谁输。

　　　第三步：第二步的重点在于记录石头数量，因为最后屏障是一个石头数量1的包围圈，这个包围圈石头数不用记录；然后所有外围石头数量总和判奇偶，奇数表示Baba要去破壁，所以Ali Win；反之同义。

失误：这里我wrong了；有两点：1）Baba Win 我写成了BaBa Win;2)第二步，我只用了（0，0）入队判断，其实不行，因为包围圈可能已经覆盖到边界了。所以要所有边界点入队判断；

#include 
#include 
#include 
#include 
#include 
#include 

---

 Ancient Messages HDU - 3839 

算法：BFS

题意：就是给你一副图，图里面有很多埃及象形字，然后图像由像素0，1构成，1表示颜色黑，0则表示白。

难点：第一点在于怎么巧妙区别埃及象形字？   每个埃及象形字都是有闭合空间并且数量对于每个埃及象形字不同，所以可以从空白入手。

　　　第二点在于如何区分埃及象形字内的空白与外空白？  这里题目给出了关键点，就是每两个埃及象形字必不连接且不嵌套。并且黑色部分永远相连不断。

思路：预处理：这里使用十六进制代表二进制像素，所以需要还原。

　　　第一步：从边界开始读空白，进行白色BFS，把所有埃及象形字的外空白标记。

　　　第二步：从上到下从左到右，找埃及象形字，遇到则开始黑色BFS，每遇到白色没标记则开始白色BFS标记；重点记录，遇到几次空白，即这个埃及象形字有多少闭合空白空间。从而区分这个是什么埃及象形字；

　　   第三步：通过BFS得出的埃及象形字数量，然后字典输出即可AC。

#include 
#include 
#include 
#include 
#include 
#include 

---

 Booksort HDU - 1685

算法：IDA* /dfs

题意：给你一个打乱顺序的序列，每次操作可以选择一个长度的 子连续序列 插入任意位置，问最少需要多少次操作变成升序序列。

　　条件就是序列的数字一定连续的数字，即 1，2，3，4，5这样的数字。然后错过4次操作的答案，一律为5 or more

　　举例：5 4 3 2 1  ------>  3 2 5 4 1 -------> 3 4 1 2 5 ------------> 1 2 3 4 5   只要3步。

思路一：题意明确只要4步以内就行了。那就使用 IDA*的dfs进行limit+1慢慢推进，直到得出答案。

　　　难点：启发函数的设定。

　　　解决：序列分块，连续的为一块，即1 4 2 3 5 序列 分成 4块 1、 4 、 23、 5；

　　　　　　这里注意， 如果第一块为1，其本身不应该算进去，因为至始至终都不会移动这一块；最末端块同理；因为 1 和 5 本身就在其最终位置上永远不需要动，

　　　　　　所以 只要改变 4，23两块就行了，即需要操作的块数为2。

　　　　      然后每次操作都会影响3块的后缀块变化，即分离块的前一块的、分离块本身与被插入点前面那块这3块的后缀；理想情况下，每次改变都使得其连接成一块，即每次操作减少3块。

　　　　　　所以1 4 2 3 5 序列 启发函数 h(x) = ceil(操作块数/3)，向下取整，即是1。

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int INF = 2e9;

int n,num[20];

void init(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>num[i];
    num[0]=0;num[n+1]=n+1;
}

void show(){
    for(int i=1;i1;i++){
        cout<" ";
    }cout<<endl;
}

int forLimit(){
    double ans = 0;
    for(int i=0;i<=n;i++) if(num[i]+1!=num[i+1]) ans++;
    return ceil(ans/3);
}

bool dfs(int step,int limit){
    int h = forLimit();
    if(h+step>limit) return false;
    if(h==0){
        cout<endl;
        //show();
        return true;
    }
    int temp[20];
    memcpy(temp,num,sizeof(num));
    for(int i=1;i<=n;i++) for(int len=1;len<=n-i+1;len++) for(int pos=1;pos<=n-len+1;pos++) if(pos!=i){
        for(int j=0;jj];
        for(int p=1,j=1;j<=n;){
            if(j];
            else if(j==pos) j+=len;
            else if(p==i) p+=len;
            else num[j++] = temp[p++];
        }
        if(dfs(step+1,limit)) {
                //memcpy(num,temp,sizeof(temp));show();
                return true;
        }
    }
    memcpy(num,temp,sizeof(temp));
    return false;
}

int main()
{
    int _;cin>>_;
    while(_--){
        init();
        for(int limit=forLimit();;limit++){
            if(limit>4) {puts("5 or more");break;}
            if(dfs(0,limit)) break;
        }
    }
}

思路二：观看大神博客https://blog.csdn.net/ilsswfr/article/details/52012467

　　　　类似于双向遍历bfs一样。

　　　　第一步：从初始序列开始dfs两步，得出答案为解。用set记录所有得出的序列。

　　　　第二部：从目标序列开始dfs两步，如果出现的序列在set里面则步数+2为解。

//从初始情况搜索两层并记录每次状态，这两层中如果有解，直接输出
//若是无解，从有序状态往回搜一层和两层，
//如果能达到与之前的相同的状态就是有解。
 
#include
#include
#include
#include
#include
#include<string>
#include
#include
#include<set>
#include

---

---

 BeatHDU - 2614 

算法：dfs

题意：给一个矩阵Tij，行为i，列为j，Tij数字为在做完第i题之后，会花费Tij时间去做第j题；这里题的难度与时间正相关。

　　　条件：1.acm大佬只做难度递增的题，即时间需要递增；

　　　　　　2.永远从第一题开始做起，而且花费时间永远为0

思路：就是从第一行开始往下dfs，需要每次都做更难或者相同难度的题。

#include 
#include 
#include 
#include 
#include 

using namespace std;

int T[20][20],n,ans;
bool ck[20];

void init(){
    memset(ck,false,sizeof ck);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>T[i][j];
    ans=1;
}

//x:上一题  y:上一题花费时间 z:总做题数
void dfs(int x,int y,int z){
    if(ans==n) return;
    if(z==n){ans = n;return ;}
    int flag = 1;
    for(int j=2;j<=n;j++) if(!ck[j]&&T[x][j]>=y){
        flag = 0;
        ck[j]=true;
        dfs(j,T[x][j],z+1);
        ck[j]=false;
    }
    if(flag) ans = max(ans,z);
    return ;
}

int main()
{
    while(cin>>n){
        init();
        ck[1] = true;
        dfs(1,0,1);
        cout<endl;
    }
}

---

---

Roll The CubeHDU - 3309 

算法：bfs

题意：给一个外边界都是墙的地图，然后里边也有墙，即障碍物；给你两个球，可以上下左右滚动一格，然后每次操作都是同步，撞墙就不能动，两个球不能重叠。地图必有两个洞，目标就是算将两个球滚进洞里　　　　的最短操作数。

思路/难点：简单的模拟题，用BFS。

　　　　　第一：BFS需要记录每一操作状态；状态有：球1坐标、球2坐标、球1进洞状态、球2进洞状态、洞1状态、洞2状态、步数。

　　　　　　　　需要维护球进洞状态：因为如果球进洞了的话，不管这么滚，坐标都不动，并且，当一个球进洞了，那么两个球是可以重叠到一个坐标上。

　　　　　　　　需要维护洞状态：判断球是否能进此洞。

　　　　　第二：排重：需要状态数组进行避免重复操作。这里因为两个球，所以就用四维数组，即球1坐标、球2坐标进行排重。不管球是否进洞都可以判断；

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n,m;
bool mp[24][24];
bool ck[24][24][24][24];
int bx[3],by[3];
int hx[3],hy[3];
int xx[]={0,0,1,-1};
int yy[]={1,-1,0,0};

void init(){
    memset(mp,true,sizeof mp);
    memset(ck,true,sizeof ck);
    cin>>n>>m;
    int bNum=0,hNum=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char ch = getchar();
            while(ch=='\n'||ch==' ') ch=getchar();
            if(ch=='*') mp[i][j]=false;
            else if(ch=='B') bx[bNum]=i,by[bNum++]=j;
            else if(ch=='H') hx[hNum]=i,hy[hNum++]=j;
    }
}

void show(){
    cout<" "<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cout<" ";cout<<endl;
    }cout<<endl;
    cout<0]<<" "<0]<<" "<1]<<" "<1]<<endl;
    cout<0]<<" "<0]<<" "<1]<<" "<1]<<endl;
    cout<<endl;
}

struct node{
    int x1,y1,x2,y2,bS1,bS2,hS1,hS2,step;
    node(int xx1,int yy1,int xx2,int yy2,int bbS1,int bbS2,int hhS1,int hhS2,int stepp)
    :x1(xx1),y1(yy1),x2(xx2),y2(yy2),bS1(bbS1),bS2(bbS2),hS1(hhS1),hS2(hhS2),step(stepp) {};
};

void change(int &x,int &y,int bS,int i){
    if(bS==1) return ;
    if(mp[x+xx[i]][y+yy[i]]) x += xx[i] , y += yy[i];
    return;
}

int check(int x,int y,int &hS1,int &hS2){
    if(hS1==0&&x==hx[0]&&y==hy[0]) {hS1=1;return 1;}
    if(hS2==0&&x==hx[1]&&y==hy[1]) {hS2=1;return 1;}
    return 0;
}

int bfs(){
    queue q;
    q.push(node(bx[0],by[0],bx[1],by[1],0,0,0,0,0));ck[bx[0]][by[0]][bx[1]][by[1]] = false;
    while(!q.empty()){
        node p = q.front();q.pop();
        for(int i=0;i<4;i++){
            int x1=p.x1,y1=p.y1,x2=p.x2,y2=p.y2,bS1=p.bS1,bS2=p.bS2,hS1=p.hS1,hS2=p.hS2;
            change(x1,y1,bS1,i);change(x2,y2,bS2,i);
            if(bS1==0&&bS2==0&&x1==x2&&y1==y2) continue;
            if(ck[x1][y1][x2][y2]==false) continue;
            ck[x1][y1][x2][y2]=false;
            if(bS1==0) bS1 = check(x1,y1,hS1,hS2);
            if(bS2==0) bS2 = check(x2,y2,hS1,hS2);
            if(hS1&&hS2) return p.step+1;
            q.push(node(x1,y1,x2,y2,bS1,bS2,hS1,hS2,p.step+1));
        }
    }
    return -1;
}

int main()
{
    int _;cin>>_;
    while(_--){
        init();//show();
        int ans = bfs();
        if(ans==-1) puts("Sorry , sir , my poor program fails to get an answer.");
        else cout<endl;
    }
}

---

---

 JerboasHDU - 2437 

算法：优先队列+BFS

题意：就是一个老鼠，他有很多个洞，TP，临时和永久两种；给你一个洞与洞的单向路径图，而且没有自身到自身的路径；给出数字K，问从S洞开始，到任意一个永久洞的最短路，并且路径长度必须为K的倍数。

思路：这里求最短路径，立马就想到BFS。

　　　1.因为洞S题目已经给出了，初始洞一定为临时洞。

           2.这里没有明确表示两个洞之间只有唯一路径，所以需要考虑两个洞存在不同长度的路径，使用二维vector存储。

           3.判重关键点，路径长度和K倍数，所以只要求路径长度对K求余的余数就能判断，K最大为1000 所以判重数组，二维只要开到1000左右，即vis[点数量][1001]。

           4.这里因为并不是简单判断最短路径，并且需要K倍数，对路径排序并没有用，所以需要优先队列，对入队的最短路进行优先出队。

我的出错点：这里我受到之前做题的影响，因为我上一道题的bfs是步骤，每次只加一，所以把判断放在了入队前也没问题。然而对于现在这题来说不行。所以需要入队完，从队列取出来再判断，再加上是优先队列，每次取出来都是最短路，只要达到要求就是答案。

#include 
#include 
#include 
#include 
#include 
#include 
#include <set>

using namespace std;

int n,m,s,k;
char dong[1002];

struct guan{
    int e,f;
    guan(int ee,int ff):e(ee),f(ff) {};
};
vector v[1002];

bool vis[1002][1001];

void init(){
    cin>>n>>m>>s>>k;
    for(int i=1;i<=n;i++){
        char ch = getchar();while(ch=='\n' || ch==' ') ch = getchar();
        dong[i] = ch;
    }
    for(int i=1;i<=n;i++) v[i].clear();
    memset(vis,false,sizeof vis);
    for(int i=0;i){
        int a,b,c;cin>>a>>b>>c;
        v[a].push_back(guan(b,c));
    }
}

struct node{
    int x,y;
    node(int xx,int yy):x(xx),y(yy) {};
    bool operator < (const node &a) const{
        if(y==a.y ) return x>a.x;
        return y>a.y;
    }
};

bool bfs(){
    priority_queue q;
    vis[s][0] = true;q.push(node(s,0));
    while(!q.empty()){
        node p = q.top();q.pop();
        int x = p.x , y = p.y;
        if(dong[x]=='P'&&y%k==0){
                cout<" "<endl;
                return true;
            }
        for(int i=0;i){
            int e = v[x][i].e , f = v[x][i].f + y;
            if(vis[e][f%k]) continue;
            vis[e][f%k] = true;
            q.push(node(e,f));
        }
    }
    return false;
}

int main()
{
    int _;cin>>_;
    for(int i=1;i<=_;i++){
        init();
        cout<<"Case "<": ";
        if(!bfs()) cout<<"-1 -1"<<endl;
    }
}

---

---

 Open the LockHDU - 1195 

算法：BFS

题意：给一个4位数，然后对位数上面的数进行操作，可以加一减一，9+1 = 1，1-1=9；可以与相邻的位数互换。

思路：简单的模拟题。因为这里只给了四位数，判重方法直接用vis[10][10][10][10]记录4个位数变化就好了

#include 
#include 
#include 
#include 
#include 
#include 
#include <set>

using namespace std;

int n[5],e[5];
bool vis[10][10][10][10];

void init(){
    memset(vis,true,sizeof vis);
    int num;cin>>num;
    for(int i=3;i>=0;i--){
        n[i] = num%10;
        num/=10;
    }
    cin>>num;
    for(int i=3;i>=0;i--){
        e[i] = num%10;
        num/=10;
    }
}

struct node{
    int t[5],step;
    node(int *a,int sstep){
        for(int i=0;i<4;i++) t[i] = a[i];
        step = sstep;
    }
    bool check(){
        if(vis[t[0]][t[1]][t[2]][t[3]]) {
            vis[t[0]][t[1]][t[2]][t[3]] = false;
            return true;
        }
        return false;
    }
    void left(int i){
        int a = t[i];
        t[i] = t[i-1];
        t[i-1] = a;
    }
    void right(int i){
        int a = t[i];
        t[i] = t[i+1];
        t[i+1] = a;
    }
    bool ansCheck(){
        for(int i=0;i<4;i++) if(t[i]!=e[i]) return false;
        return true;
    }
};

int bfs(){
    queue q;
    q.push(node(n,0));
    vis[n[0]][n[1]][n[2]][n[3]] = false;

    while(!q.empty()){
        node p = q.front();q.pop();

        if(p.ansCheck()) return p.step;

        for(int i=0;i<4;i++){
            //==============================
            node temp = p;temp.step++;
            if(temp.t[i]==9) temp.t[i] = 1;
            else temp.t[i]++;
            if(temp.check()) q.push(temp);
            //==============================
            temp = p;temp.step++;
            if(temp.t[i]==1) temp.t[i] = 9;
            else temp.t[i]--;
            if(temp.check()) q.push(temp);
            //==============================
            temp = p;temp.step++;
            if(i!=0){
                temp.left(i);
                if(temp.check()) q.push(temp);
            }
            //==============================
            temp = p;temp.step++;
            if(i!=3){
                temp.right(i);
                if(temp.check()) q.push(temp);
            }
        }
    }

    return -1;
}

void show(){
    for(int i=0;i<4;i++) cout<" ";cout<<endl;
    for(int i=0;i<4;i++) cout<" ";cout<<endl;
}

int main()
{
    int _;cin>>_;
    while(_--){
        init();//show();
        cout<endl;
    }
}

---

---

 Pushing Boxes POJ - 1475 

算法：BFS

题意：推箱子游戏，游戏规则：人只能有两个操作，一个就是走，另一个就是推箱子。目标就是把箱子推到目标位置。然后求 推操作数量最小 为前提 的 最短路径。

思路1：这个是我想的，直接用优先队列，每个点记录，人位置、箱子位置、推的数量、步数；然后优先 推数量 最小 在前面，然后相同则步数最小。

　　     排重这里我用 [ 人X坐标 ] [ 人Y坐标 ] [ 箱子X坐标 ] [ 箱子Y坐标 ] [ 推数量 ] 五维数组维护，然后TL了。后面把推数量去掉，就ac了。

　　（这里想了一下，优先队列已经维护了推数量最少，排重数组不需要维护，因为之前出现过推数量，在人与箱子相对位置的情况下，必为最优；即先存在为最优）

　　　然后唯一注意的点是，这里输出答案 两个之间有一个空行。没留意，wrong了很多次。看了人家代码才发现。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int INF = 2e9;

int n,m;
int Sx,Sy,Bx,By,Tx,Ty;
bool mp[21][21];
bool vis[21][21][21][21];
int xx[] = {0,0,-1,1};
int yy[] = {1,-1,0,0};
char fch[] = {'e','w','n','s'};
char bch[] = {'E','W','N','S'};

bool checkXY(int a,int b){
    if(a<=0||b<=0||a>n||b>m) return false;
    return mp[a][b];
}

struct node{
    int a,b,c,d,step,p;
    string ans;
    node(int aa,int bb,int cc,int dd,string ss,int sstep,int pp):a(aa),b(bb),c(cc),d(dd),ans(ss),step(sstep),p(pp) {};
    bool check(){
        if(c==Tx&&d==Ty) return true;
        return false;
    }
    bool operator < (const node &x) const{
        if(p==x.p) return step>x.step;
        return p>x.p;
    }
};

void init(){
    memset(mp,true,sizeof mp);
    memset(vis,true,sizeof vis);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        char ch=getchar();while(ch=='\n') ch=getchar();
        if(ch=='#') mp[i][j] = false;
        else if(ch=='S') Sx=i,Sy=j;
        else if(ch=='B') Bx=i,By=j;
        else if(ch=='T') Tx=i,Ty=j;
    }
}

void show(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cout<" ";cout<<endl;
    }
}

bool bfs(){
    priority_queue q;
    q.push(node(Sx,Sy,Bx,By,"",0, 0));
    vis[Sx][Sy][Bx][By] = false;
    while(!q.empty()){
        node p = q.top();q.pop();
        if(p.check()){
            cout<endl;
            return true;
        }
        for(int i=0;i<4;i++){
            node u = p;u.a += xx[i],u.b += yy[i];
            if(!checkXY(u.a,u.b)) continue;
            bool flag = false;
            if(u.a==u.c&&u.b==u.d) flag = true;
            if(flag){
                u.c += xx[i],u.d += yy[i];
                if(!checkXY(u.c,u.d)) continue;
                if(!vis[u.a][u.b][u.c][u.d]) continue;
                vis[u.a][u.b][u.c][u.d] = false;
                u.ans+=bch[i];
                u.step++;
                u.p++;
                q.push(u);
            }else{
                if(!vis[u.a][u.b][u.c][u.d]) continue;
                 vis[u.a][u.b][u.c][u.d] = false;
                 u.ans+=fch[i];
                 u.step++;
                 q.push(u);
            }
        }
    }
    return false;
}

int main()
{
    int cas = 1;
    while(cin>>n>>m&&n&&m){
        cout<<"Maze #"<endl;
        init();
        if(!bfs()) puts("Impossible.");
        cout<<endl;
    }
}

---

思路2：这个是看别人博客学的。http://t.zoukankan.com/xiaoguapi-p-10389623.html

　　　　大意就是进行一次箱子到目标位置的BFS求最短路径，然后在箱子BFS内部嵌套一个人推箱子的BFS求人到箱子位置的最短路径。

　　　重点：1.箱子每一步，都要去BFS判断人能不能走到箱子上一步位置，不行则箱子走不了。2.判重，外围bfs只需要维护箱子位置就行，内部每一次BFS判重也只维护人的位置即可。

            代码详情看大神博客。

---

---