题解 P4667 【[BalticOI 2011 Day1] 电路维修】

· · 题解

拿到题目，先看要求：emmmm......地图（迷宫？），最短路径......这题思路就有了：没毛病！bfs就完了！

底下肯定有同学高兴坏了：“不就是bfs嘛！bfs我会！这题我肯定不出30秒就AC了！哈哈哈哈！”行，既然你说这题只用bfs就能AC，那你过来搜一下试试！

从起点开始，沿路走到A点，A可以直达B点，又可以经过一步转向到C、D点

B点出发，可以到E（转向）、A、F、G（直达）；

然后再从C、D、E出发.....

2000 years later......

所以说嘛，这题只用bfs肯定是不行滴，不光搜索路径费时费力，最后还要考虑步数的更新，正确答案需要搜索很久很久很久之后才可以搜出来，有没有什么解决的方法呢？？？

别慌，我们再来看一下题目：每条电线要么需要转向，要么不需要转向，如果不用转向就能走通，那还转向干嘛！不转向的情况，肯定是比转向要好的

好吧，我承认上一句是句废话，不过从上一句我们可以得到：如果搜索的时候先搜不转向的，再搜转向的，那正确答案肯定会来的快很多

想得倒是挺美，但到底怎样才能实现这一顺序呢？？？普通的先进先出的队列虽好，但肯定不能玩这么神奇的操作，不过咱们可以用另外一种“升级版”的队列——双端队列！

所谓双端队列，顾名思义，就是可以在两端同时进行操作的队列，我们知道，普通的队列，只能从队尾进，队首出，而双端队列，在队首和队尾都能进行入队和出队的操作，想怎么玩，就怎么玩！

有了这双端队列，这题就好办了：如果不需要转向，那就从队首入队，这样就可以先搜到，需要转向就在队尾入队，搜完了不转向的才会搜这些，出队的话就统一从队首出去就好啦！

这么好的东西，到底怎么实现呢？别忘了咱们c++有一个神奇的百宝袋——STL，我们从这个“万能口袋”里挑一个......就你啦，deque！

至于这个deque，也不是多难，如果你会vector或queue的相关操作，那deque的使用对你来说就及其轻松愉快了，来，让我们看一下deque的相关操作：
deque <int> q 定义一个int（当然可以换成别的）类型的名为q的deque
q.push_front(x) 从q的队首将x入队
q.push_back(x) 从q的队首将x入队（有没有感觉跟vector迷之相似呢）
q.pop_front() 将队首的元素出队
q.pop_back() 将队首的元素出队（vector：？？？？？）
q.front() get到队首元素（这回轮到queue感叹迷之相似了）
q.empty() 判断这个deque空不空，空返回1，不空返回0(queue...)

（c党和p党不要走开，你们虽然没有STL，但也可以手写呀，

如果有n个点，开一个长度为2*n的数组，

一开始把队首head和队尾tail都放在n的位置，

队首入队head--，队尾入队tail++，出队head++，

一样可以过这个题！）

到这里，这题的基本思路就有了:从起点开始用广搜方法走向终点，判断经过的电线要走的方向是否跟原图的方向一致，（不一致就要转向啦），如果要转向，队首入队，步数+1，要不然队尾入队，步数还是原来的不变（每个格子的步数咱可以用一个int二维数组记录哦！），和普通的bfs一样，搜到deque为空为止

思路有了，接下来就是细节决定成败了，这题细节真的很重要！

细节 1：格子图?点图?

通过观察我们发现，这个题目里面，我们是看每一个点是否联通，还用格子来判断电线的位置，所以这个题我们要像机器人搬重物一样把格子图转化成点图，不光要转化，还要分别处理（我这边是从0开始存的，下图黄色数字代表点坐标，绿色数字代表格子坐标）

细节 2：方向数组？？？

广搜嘛，一定要有一个叫方向数组的东西，但是这里的的方向数组不大一样：

  1. 平常我们是上下左右走过去，但这里呢，电路的电线是沿斜线走的
  2. 前面说了，要将格子和点分别处理，所以我们要弄两个方向数组，一个控制格子，另一个控制点

  3. 因为我们要判断是否需要转向，而题目里电线的状态是以字符的形式给出的，所以我们还要搞一个字符数组，来获取走这个方向时电线的状态

从这个图就可以看出点、格子和电线的方向了，我们就可以这样定义方向数组：

（由于'\'是转义字符，比如'\n'是换行，如果要用到'\'这个字符的时候，我们需要用'\\'来表示）

const int dx[4]={1,-1,-1,1};  //dx和dy是点的方向数组
const int dy[4]={1,1,-1,-1};
const char a[5]="\\/\\/";  //字符数组表示电线在各个方向的状态
const int ix[4]={0,-1,-1,0};  //ix和iy是格子的方向数组
const int iy[4]={0,0,-1,-1};

细节 3：什么时候入队？？？

这也是一个很坑的设定：什么时候从队首/队尾入队已经在前面强调了2147483647遍了，但只注意这个就完了吗？？

No，如果搜到顶点就入队，那只会让你死循环（亲测）

这里直接告诉大家：只有新算出来的步数比原来的少的时候，才能入队！！！

还要注意一个问题，就是当你get到队首顶点的时候，要先把它pop出去（否则你从队首入队的话，刚进去就出来了，程序就会反复搜同一个点，亲测死循环）

细节 4：无解的情况怎么判断？

这个题还有一种情况，就是“NO SOLUTION”，这个具体来说就很好办了： 做过八皇后的小伙伴们都知道：沿对角线走的时候，坐标的和/差是不变的，这里我们延伸一下：沿对角线走的时候，坐标之和的奇偶性是不变的

知道了这个结论，那就很好办了，由于这里是固定从（0，0）出发，横纵坐标和是偶数，所以只要终点的横纵坐标和是奇数，那必定 NO SOLUTION.

所以我们在输入完的时候，就可以直接把NO SOLUTION 的情况判断出来，确定有解之后再搜索~

细节 5：其它你需要注意到的一切细节

好多要注意的前面也都说了，像判断路线要写两个反斜杠，还有方向数组队列的那一套......

还有一个要注意的：这个题变量那么多，一定要擦亮眼睛，别写混了

（本蒻才不会告诉你我卡了三小时就是因为一个y写成x了呢）

学会了方法，注意了细节，最后就一定能AC了，祝屏幕前的小可爱们AC这个题！

#include<iostream>
#include<deque> //头文件啥的就不用我说了吧
#include<cstring>
using namespace std;
const int dx[4]={1,-1,-1,1}; //方向数组，别搞错了
const int dy[4]={1,1,-1,-1};
const char a[5]="\\/\\/";
const int ix[4]={0,-1,-1,0};
const int iy[4]={0,0,-1,-1};
deque <int> x;  //双端队列！
deque <int> y;
char map[505][505]; //存储地图
int vis [505][505]; //vis数组，记录最短步数
int l,c;  //l——line（行数），c——column（列数）
void I_love_luogu(){  //广搜函数
    memset(vis,0x3f,sizeof(vis)); //因为要求最小值，把vis数组初始化成0x3f（就是一个很大的数啦）
    x.push_back(0);  //起点（0，0）入队，步数是0
    y.push_back(0);
    vis[0][0]=0; 
    while(!x.empty()){  //这一部分就是把广搜的板子啦
        int xx=x.front();  //先get到队首
        int yy=y.front();
        x.pop_front();  //一定要get完了之后先pop出去
        y.pop_front();
        for(int i=0;i<4;i++){  //4个方向一个一个试
            int dnx=xx+dx[i]; //dnx，dxy——点的横纵坐标
            int dny=yy+dy[i];
            int inx=xx+ix[i];//inx，iny——格子的横纵坐标
            int iny=yy+iy[i];
            if(dnx>=0&&dnx<=l&&dny>=0&&dny<=c){  //如果没出界的话就考虑入不入队
                if(a[i]!=map[inx][iny]){ //看看地图的电线状态和往这个方向走的电线状态是否一致
                    int t=vis[xx][yy]+1;  //不一致就要转向，步数+1
                    if(t<vis[dnx][dny]){ //如果比原来的步数小，就入队，标记
                        x.push_back(dnx); //转向肯定不如不转向好，所以要后搜，从队尾入队
                        y.push_back(dny);
                        vis[dnx][dny]=t;    
                    }
                }   
                else{//要不就不用转向
                    int t=vis[xx][yy] //不用转向，步数不用变;
                    if(t<vis[dnx][dny]){ //步数比原来的小才能入队
                        x.push_front(dnx); //不用转向肯定更好，要先搜，从队首入队
                        y.push_front(dny);
                        vis[dnx][dny]=t;    
                    }
                }
            }
        }
    cout<<vis[l][c]<<endl; //输出最后的步数
}
int main(){
        cin>>l>>c; //输入
        for(int i=0;i<l;i++)
            cin>>map[i];
        if((l+c)%2) //如果终点横纵坐标和是奇数
        cout<<"NO SOLUTION\n";//那就铁定无解
        else I_love_luogu(); //不无解那就广搜
    return 0;       
}

A了这个题，相信小伙伴们对双端队列的认识和应用有了一定基础了，不过还有个问题：究竟什么时候才需要用到双端队列呢？？？

答案很简单：只要搜索的东西存在一个优先级（比如这个题里的要转向和不用转向），那用一个双端队列就是最好的选择啦

如果理解了这一点，再给你们推荐道题：Labyrinth

也是用双端队列解决，好好思考吧！（说句实话，这题更简单）

最后：特别鸣谢

Mr_yin 老师：提供思路

vectorwyx 奆佬：帮忙查错

The End!