题解 P6474 【[NOI Online #2 入门组]荆轲刺秦王】

· · 题解

做题之前，让我们先大喊两句：

\bold{\sout\text{ 荆轲，你刺秦王的英勇事迹将会被全天下的OIers怀恨在心}} \bold{\Large\xcancel\text{荆轲将会臭名昭著}}

好了，发泄完啦，让我们开始认真做题吧！

一看题目，像个搜索

再一看，像个广度优先搜索

既然是BFS，那我们首先要搞出一个（一堆）队列

那问题是队列里咱们存啥呢？？？

首先，按照广搜解决“迷宫问题”的国际惯例，肯定要先把坐标和步数存到里面！

可是，这似乎不大够？

遇到问题不要怕，微笑着面对它，从题目中找答案！

荆轲还有两种技能：隐身和瞬移。

  1. 隐身：balabala……
  2. 瞬移：balabala……

现在给出咸阳城的地图，请计算荆轲到达秦王所在点所需的最短时间。此外，在所用时间相同情况下，荆轲希望使用的两种技能总次数尽可能少；在所用时间与技能次数相同情况下，荆轲希望使用的隐身次数尽可能少。

emmmmm，还要把隐身和瞬移的使用次数存下来~

啊，要存这么多东西……这时候，结构体就要派上用场啦！

（结构体是哪位？不是哪位，是用这玩意写高精特别方便的那个结·构·体！）

struct qwq{
    int x,y,yx,sy,s;
    //x,y——对应的坐标
    //s——走到这一步的步数
    //yx——隐形使用次数
    //sy——瞬移使用次数
    //（都是用拼音写的呢）
};
queue <qwq> q;//STL超级方便！就是常数大那么亿点

当然，我们要在茫茫多的方案中选择一个最优解——所以，我们要写一个函数（算是取min吧……），来选择一个最优解

qwq minq(qwq a,qwq b){
    if(a.s!=b.s)return a.s<b.s?a:b;//优先选择步数更小的
    if(a.yx+a.sy!=b.yx+b.sy)return a.yx+a.sy<b.yx+b.sy?a:b;//如果步数相等，选择一个技能使用更少的
    return a.yx<b.yx?a:b;//都相等？！那就选一个隐身用的更少的吧
}
qwq ans=(qwq){0,0,233333333,233333333,233333333};//顺便把初始化的ans放出来，当然要挑个大的

所有结构体啥的准备工作都已经完成啦！接下来，咱们考虑一下main函数的框架：包括输入等细节的处理

especially，咱们来康康要输入要注意啥：

  1. 输入的整个地图，既有诸如 S T . 之类的字符，还有表示卫兵监控范围的数，两个这么一整合——就用string来输入吧！
  2. 由于S啊，T啊啥的随便换个数就行了，只要能标记上就OK，而地图上的数字是非常重要的，所以地图我们用int类型存储
  3. 这应该也是每个字符串模拟题要注意的地方，当输入到字符串里的数字\ge10的时候，我们要一位一位加上去，（写的时候可以照快读那样写），千万不要读完一位剩下的就不管了
  4. 对于每种字符的特殊处理——标记起点和终点，遇到卫兵时，我们要处理出卫兵的观察范围

呼呼，大概就这么多啦~

int n,m,c1,c2,d;//题目描述里的一堆东西
int map[355][355];//地图
int main(){
    ios::sync_with_stdio(false);//关闭流同步，让cin变得快快哒！
    cin>>n>>m>>c1>>c2>>d;//据说cin和scanf混用会出锅？统一用cin
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            string s;
            cin>>s;
            if(s[0]=='S'){//起点
                sx=i,sy=j;//找到起点坐标
                map[i][j]=-1;//标个记
                q.push((qwq){sx,sy,0,0,0});//放到队列里~！
                vis[i][j][0][0]=1;//起点的vis先变成1（vis为啥要开四维？待会再说！（可能大家都已经想到了））
            }
            else if(s[0]=='T'){//终点~
                ex=i,ey=j;//找坐标
                map[i][j]=-2;//标个记
            }
            else if(s[0]=='.')map[i][j]=0;//平凡的空地就不用处理啦
            else{//S，T和.都不是，那就是卫兵啦
                int x=0;//数字读进来
                for(int i=0;i<s.size();i++)
                x=(x<<1)+(x<<3)+(s[i]^'0');//类比快读的原理
                map[i][j]=x;//存到地图里
                lookaround(i,j,x-1);//处理出这只士兵的观察范围，待会讲（重点！）
            }
        }
    }
    bfs();//baidu_first_search（伦敦大雾）
    if(ans.s==233333333)printf("-1");//如果ans没变，那就走不通了
    else printf("%d %d %d",ans.s,ans.yx,ans.sy);//否则输出
    return 0;//功德圆满
}

那接下来的问题来啦！如何处理每个士兵的监控范围呢？

\large{\text{（前排提示：敲黑板，划重点！！！）}}

暴力找周围曼哈顿距离<a的点？

时间复杂度O(a^2)，加上输入的循环O(a^2mn)，TLE警告……

那咋办呢？别急，正所谓“举例是理解的试金石”（话说我这是第几次用这句话了……反正好久没用了），咱们先画个图！

下图就是a=3的情况，士兵可以观察到和它的曼哈顿距离\le2的点

（图中，\bold{\text{黑色}}点为士兵所在点，\bold{\color{purple}\text{紫色}}点为士兵的监控范围点）

我们惊奇地发现，覆盖区域是一个实心的菱形！

也就是说，士兵观察到的范围，对每一行/列来说，都是一段连续的区间！ 处理范围，是一个区间修改问题！

提到区间修改，大家会想到什么呢？

线段树？……树状数组？……差分！

众所周知，差分在区间修改问题中有奇效，原因是它只需要改——两个点（不知道为啥？翻我之前题解去，you can also 翻我小伙伴的题解）， 我们只需要在左端点的位置+1，右端点+1的位置-1

而且，既然区域是个菱形，我们可别忘了菱形的对称性，也就是说，我们找到一个点之后，我们可以根据它的两条对称轴找到它的三个对应点

也就是说，我们能在O(a)的时间内求出一个士兵的监控范围，处理这一块的总复杂度为O(amn)，不错不错~

我这里采用的是从中心向四周扩展的方式——也就是说枚举当前点到中心的距离进行修改

（图中，\bold{\color{green}\text{绿色}}点为修改的左端点，\bold{\color{orange}\text{橙色}}点为修改的右端点，为了符合我们OIer的坐标书写习惯，x轴正方向为下方，y轴正方向为右方）

结合着这个图，你就可以理解下方的代码惹~

在写代码之前，我再bb两句：

  1. 差分修改时右端点别忘了加1！！！！！
  2. 注意边界的问题，如果超范围了，那就把修改加到边界上（比如右端点为n+3，超范围了，那就把这一块的修改改成n，左端点同理）
bool look[355][355];//look为能不能看到
int tag[355][355];//tag就是差分数组
void lookaround(int x,int y,int k){//x,y为士兵的坐标，k就是士兵的a值
    for(int i=0;i<=k;i++){//从里向外扩展（由于我们调用的时候已经把k减1了，所以我们这里就是<=k，这样很好写）
        //利用刚才找到的规律进行修改吧！
        //如果理解不了，自己再画图找规律
        tag[max(x-i,1)][max(y-(k-i),1)]++; 
        tag[max(x-i,1)][min(y+(k-i),m)+1]--;
        tag[min(x+i,n)][max(y-(k-i),1)]++;
        tag[min(x+i,n)][min(y+(k-i),m)+1]--;
        //最后别忘了：注 意 细 节
    }
}

那我们如何用tag数组判断一个点是否在士兵的监视范围之内呢？

别忘了：差分的前缀和就是它本身！（自己根据差分和前缀和的定义推一下？）

也就是说，我们对tag数组求一遍前缀和，只要这个和>0，就能被看到啦！

我们只需要在main函数里加上这几句：

    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=m;j++){
            sum+=tag[i][j]; //就是一个前缀和
            if(sum>0)look[i][j]=1;  
        }
    }

接下来，就是我们的重头戏——广搜的过程啦！

其实只要注意一些细节啥的，广搜根本就不难写

（本题解沿用了vectorwyx同学提供的思路，让我们一起感谢他！）

起初，神创造bfs。

队列是空虚混沌，渊面黑暗；神的灵运行在队首上。

while(!q.empty()){
        qwq fro=q.front();
        q.pop();
        if(fro.s>ans.s)continue;//最优性剪枝！一定要加上不然会T
        if(fro.x==ex&&fro.y==ey){//找到重点
            ans=minq(ans,fro);//更新最优解
            continue;//之后就没必要搜啦
        }      
        //do something……
}

神说：“要有方向数组”，就有了方向数组。

const int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};//八连通的方向数组
//为了方便瞬移操作，前四个是上下左右，后四个是斜线

神看瞬移是好的，就把方向数组的前后分开了。有晚上，有早晨，是第一日。

        for(int i=0;i<8;i++){//不瞬移，按照八连通方向
        int nx=fro.x+dx[i];//沿着方向数组走
            int ny=fro.y+dy[i];
            //do something...
        }
        if(fro.sy+1>c2)continue;//在瞬移之前，先看看能不能再使用瞬移
        for(int i=0;i<4;i++){//瞬移只能走上下左右
          int nx=fro.x+dx[i]*d;//一次可以走d格
             int ny=fro.y+dy[i]*d;   
            //do something...
        }

　神说，士兵的监控范围内要隐身，神就造出判断条件，将隐身的处理，不隐身的处理分开了。事就这样成了。

    if(look[nx][ny]){//如果要走的地方在士兵的监控范围内，需要隐身
        if(vis[nx][ny][fro.yx+1][fro.sy]||fro.yx+1>c1)continue;//如果这个状态到过了，或者超过了隐身使用次数，continue
        vis[nx][ny][fro.yx+1][fro.sy]=1;//vis变为1
        q.push((qwq){nx,ny,fro.yx+1,fro.sy,fro.s+1});//push进去的时候别忘了把隐身次数+1
    }
    else{//不需要隐身就不用判断隐身的使用次数，隐身数也不用+1
        if(vis[nx][ny][fro.yx][fro.sy])continue;
        vis[nx][ny][fro.yx][fro.sy]=1;
        q.push((qwq){nx,ny,fro.yx,fro.sy,fro.s+1});             
    }
   //瞬移的也如法炮制，只要记得把瞬移数+1就OK

神又加了防止越界的措施，有晚上，有早晨，是第二日。

    if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;//如果越界了/这个位置是士兵，不能走
\cdots\cdots

不行了不行了我编不下去惹……咱们直接来看完整代码吧！

void bfs(){
    while(!q.empty()){
        qwq fro=q.front();//取队首
        q.pop();//pop
        if(fro.s>ans.s)continue;//最优性剪枝
        if(fro.x==ex&&fro.y==ey){//判断终点
            ans=minq(ans,fro);//更新答案
            continue;
        } 
        for(int i=0;i<8;i++){
            int nx=fro.x+dx[i];
            int ny=fro.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;
            if(look[nx][ny]){//不瞬移+隐身
                if(vis[nx][ny][fro.yx+1][fro.sy]||fro.yx+1>c1)continue;
                vis[nx][ny][fro.yx+1][fro.sy]=1;
                q.push((qwq){nx,ny,fro.yx+1,fro.sy,fro.s+1});
            }
            else{//不瞬移+不隐身
                if(vis[nx][ny][fro.yx][fro.sy])continue;
                vis[nx][ny][fro.yx][fro.sy]=1;
                q.push((qwq){nx,ny,fro.yx,fro.sy,fro.s+1});             
            }
        }
        if(fro.sy+1>c2)continue;
        for(int i=0;i<4;i++){
            int nx=fro.x+dx[i]*d;
            int ny=fro.y+dy[i]*d;
            if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;
            if(look[nx][ny]){//瞬移+隐身
                if(vis[nx][ny][fro.yx+1][fro.sy+1]||fro.yx+1>c1)continue;
                vis[nx][ny][fro.yx+1][fro.sy+1]=1;
                q.push((qwq){nx,ny,fro.yx+1,fro.sy+1,fro.s+1});
            }
            else{//瞬移+不隐身
                if(vis[nx][ny][fro.yx][fro.sy+1])continue;
                vis[nx][ny][fro.yx][fro.sy+1]=1;
                q.push((qwq){nx,ny,fro.yx,fro.sy+1,fro.s+1});               
            }           
        }
    }

所有的地方都讲完啦！我们来看看完整代码吧！

注意：如果你的代码被卡常而TLE了，请用 C艹17 吸氧提交

（据说是因为新版本的编译器用 STL 会更快？）

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct qwq{//qwq结构体
    int x,y,yx,sy,s;
};
qwq minq(qwq a,qwq b){//找最优解
    if(a.s!=b.s)return a.s<b.s?a:b;
    if(a.yx+a.sy!=b.yx+b.sy)return a.yx+a.sy<b.yx+b.sy?a:b;
    return a.yx<b.yx?a:b;
}
bool vis[355][355][20][20],look[355][355];//一堆杂七杂八的东西
int tag[355][355];
int n,m,c1,c2,d;
int map[355][355];
const int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
void lookaround(int x,int y,int k){//处理看到的范围（差分数组tag）
    for(int i=0;i<=k;i++){
        tag[max(x-i,1)][max(y-(k-i),1)]++; 
        tag[max(x-i,1)][min(y+(k-i),m)+1]--;
        tag[min(x+i,n)][max(y-(k-i),1)]++;
        tag[min(x+i,n)][min(y+(k-i),m)+1]--;
    }
}
int sx,sy,ex,ey;
queue <qwq> q;//队列
qwq ans=(qwq){0,0,233333333,233333333,233333333};
void bfs(){//广搜
    while(!q.empty()){
        qwq fro=q.front();
        q.pop();
        if(fro.s>ans.s)continue;
        if(fro.x==ex&&fro.y==ey){
            ans=minq(ans,fro);
            continue;
        } 
        for(int i=0;i<8;i++){
            int nx=fro.x+dx[i];
            int ny=fro.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;
            if(look[nx][ny]){
                if(vis[nx][ny][fro.yx+1][fro.sy]||fro.yx+1>c1)continue;
                vis[nx][ny][fro.yx+1][fro.sy]=1;
                q.push((qwq){nx,ny,fro.yx+1,fro.sy,fro.s+1});
            }
            else{
                if(vis[nx][ny][fro.yx][fro.sy])continue;
                vis[nx][ny][fro.yx][fro.sy]=1;
                q.push((qwq){nx,ny,fro.yx,fro.sy,fro.s+1});             
            }
        }
        if(fro.sy+1>c2)continue;
        for(int i=0;i<4;i++){
            int nx=fro.x+dx[i]*d;
            int ny=fro.y+dy[i]*d;
            if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]>0)continue;
            if(look[nx][ny]){
                if(vis[nx][ny][fro.yx+1][fro.sy+1]||fro.yx+1>c1)continue;
                vis[nx][ny][fro.yx+1][fro.sy+1]=1;
                q.push((qwq){nx,ny,fro.yx+1,fro.sy+1,fro.s+1});
            }
            else{
                if(vis[nx][ny][fro.yx][fro.sy+1])continue;
                vis[nx][ny][fro.yx][fro.sy+1]=1;
                q.push((qwq){nx,ny,fro.yx,fro.sy+1,fro.s+1});               
            }           
        }
    }
}
int main(){//main函数
    ios::sync_with_stdio(false);
    cin>>n>>m>>c1>>c2>>d;
    for(int i=1;i<=n;i++){//输入+处理
        for(int j=1;j<=m;j++){
            string s;
            cin>>s;
            if(s[0]=='S'){
                sx=i,sy=j;
                map[i][j]=-1;
                q.push((qwq){sx,sy,0,0,0});
                vis[i][j][0][0]=1;
            }
            else if(s[0]=='T'){
                ex=i,ey=j;
                map[i][j]=-2;
            }
            else if(s[0]=='.')map[i][j]=0;
            else{
                int x=0;
                for(int i=0;i<s.size();i++)
                x=(x<<1)+(x<<3)+(s[i]^'0');
                map[i][j]=x;
                lookaround(i,j,x-1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=m;j++){
            sum+=tag[i][j]; //求出look数组（前缀和）
            if(sum>0)look[i][j]=1;  
        }
    }   
    bfs();//广搜
    if(ans.s==233333333)printf("-1");
    else printf("%d %d %d",ans.s,ans.yx,ans.sy);//最后输出
    return 0;
}
\huge{\mathscr{\color{magenta}THE}} \huge{\mathscr{\color{springgreen}END}}

（顺便祝大家开学快乐鸭www）