题解 P3956 【棋盘】

update on 2020.2.16

看到评论区有同学对排版的建议，故对文章排版进行一些优化，使本题解符合现行题解规范。

写在前面

这是本蒟蒻一年前发的题解，因此有些地方讲的不是特别清楚，代码也比较冗长。其实这一题没有必要将其转换为图论模型，在上面跑最短路，可以直接使用优先队列优化的 BFS 。

NOIP2017普及组比赛，是我参加的第一次复赛，当时我太菜了（虽然说现在的我也还是很菜），这一题最暴力的 dfs 都写不对，不知怎么拿到了20分，其余的测试点 WA+TLE ，在考场上时间几乎全用来氪这一题，结果最后一题想出50分 DP 没调完，220滚粗。考场上主要纠结于如何处理魔法，因此考后和同学想到了这样一种代替魔法的算法。

这一次修改，将对原题解中解释的不是很清楚的地方作较为清晰的解释，并且修改了最后的参考程序，提供本题2种做法。

至于本题的主流算法（ dfs +记忆化优化），其实从最短路的角度上来讲是基于 dfs 实现的 SPFA （没错，就是那个死了又活了的SPFA）,如果这一题数据范围扩大，并且做一些特殊构造，是可以被卡掉的。

另外，本蒟蒻不建议使用基于 dfs 实现的 SPFA ，因为这其实是最好卡掉了 SPFA 。

题意分析与转化

给你一个棋盘，有一些格子被染成了两种颜色。你可以从一个有颜色的格子走向另一个有颜色的格子，若两个格子颜色相同，则不付出代价，否则付出 1 点代价。

如果题目就到这里，相当于代价为 0 或者 1 的四个方向的走迷宫，可以使用双端队列 BFS 实现，时间复杂度O(m^2)

另外， 你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。

如果就按照题意来直接搜索的话会比较麻烦（本蒟蒻当年就是这样写挂了的），但是我们可以稍微转化一下。

（注：下面的分析过程不妨只考虑一种颜色，因为颜色不同带来的代价的变化和魔法的转化没有太大关系）

我们现在站在一个施了魔法的格子上(称为 via )，我们上一步的格子称为 now ，下面我们思考下一步能走到的格子有哪些（称为 next ）。

因为魔法不能连用，并且如果我们走回上一步的格子，结果一定不是最优的，所以我们可以选择的只有如下的情况：

其中蓝色的格子可能成为 next （前提，在未使用魔法的情况下这些格子本来有色）。

知道了 next 可能的决策集合，我们下面来看如何把魔法等价转换掉。

如图，可以将格子 via 施加魔法，从 now 走向 next ，实现了向右下方的转移。

如图，可以将格子 via 施加魔法，从 now 走向 next ，实现了向左下方的转移。

如图，可以将格子 via 施加魔法，从 now 走向 next ，实现了向下连跳2格的转移。

如图，可以将格子 via 施加魔法，从 now 走向 next ，实现了向右连2格的转移。

同理，我们也可以实现向左上方，向右上方，向上连跳2格，向左连跳2格的转移。

综上，我们得到使用魔法可以转移到的情况：

综合一下，我们可以得到如下结论：从 now 这个格子出发，使用或不使用魔法可以走到的有色格子的情况如下图：

其中绿色格子因为使用魔法，不需要花费代价，蓝色的格子因为使用一次魔法，需要额外花费 2 点代价。（同样，这里不考虑格子实际颜色对代价的影响）

也许有同学会问了，如果出现下图中的这种情况呢？

显然从 now 出发先向右走后向下走是更优的，但是按照我们刚刚所述的方法，对 now 这个格子讨论，右下角的有色格子 B 会被认为要使用魔法，凭空多出了2点代价，我们刚刚的方法能得到最优解吗？

试问： now 右面的格子 A 是不是有色格子？

既然 A 是有色格子，那么我们也会对 A 讨论， now 可以不花费代价到达 A ， A 又可以不花费代价到达 B ，因此 now 到 B 格子的代价最终会被 now->A->B 的路径取代，不会出现丢失最优解的情况。

这时我们发现一个问题：普通的 BFS 似乎实现不了这种答案更新，具体的分析与解法将在下文讲解。

现在我们先把颜色加上去：

1. 与魔法无关的4种转移，同色代价不变，异色代价加 1 。
2. 涉及魔法的8种转换，如果颜色相同，如图：

当格子 via 变成黄色的格子的时候，付出的代价最小，一共为2个代价。

如果颜色不同，如图：

当格子 via 变成黄色或者红色的时候，付出的代价都是一样的，一共为3个代价。

综上所述，我们将题目转化为如下：

你需要从(1,1)走到(m,m)，你只能走在有颜色的格子中，并且使得你所花费的代价最小。

当你站在一个有颜色的格子上的时候，你可以进行如下2种操作：

1. 向上、下、左、右前行。
2. 向左上、左下、右上、右下、向上连跳2格、向下连跳2格、向左连跳2格、向右连跳2格前行。

如果你使用的是操作 2 ，你将额外付出 2 点代价。

在一次操作中，如果你这次操作的起点格子与终点格子颜色不同，你将付出1点代价。

完了吗？

显然没有！

如果(m,m)没有颜色怎么办？

因为魔法不能连续使用，所以只可能从(m,m-1)，(m-1,m)转移。

1. 如果都没有颜色，就不可能到达(m,m)。
2. 如果任何一个有颜色，相当于(m,m)变化为有颜色的那个格子的颜色，总代价为2。
3. 如果2个都有颜色，转移总代价都是2，最后做一下比较就可以了。

算法分析

下面我们主要研究 BFS 的实现。

现在我们已经将题意转化为经典的走迷宫模型，解决的经典方法是 BFS ，但是又有所不同。每一次拓展的代价不一定相同，此时可能出现如下的情况：

因为不满足三角形不等式，所以从实际来讲这里不应该画成三角形。但因为这张图简(wo)明(bi)直(jiao)观(lan)，所以这张图就不重画了。

显然，最短路径应该是 1->2->3 ，而如果我们用一般的队列实现宽搜，就会得到错误的答案。

我们先思考一个问题：为什么经典的走迷宫模型可以直接普通队列 BFS ？

不难得出：在这样的 BFS 中，每一次扩展的代价都相等且为正数，后进入队列的状态一定不如先进入队列的状态优（先进入队列的状态的代价 \le 后进入队列的状态的代价）。

基于这样的单调性，我们可以得出：第一次访问到某一个状态时，一定是这个状态的最优情况。

这是一个贪心思想。我们把这种思想应用到更具有普遍性的情况中：代价不一定相等。

现在我们有2种解决方法：

• 普通队列+迭代思想(已经死掉的SPFA)

我们无法保证第一次访问到某一个状态的最优性，但我们可以将被优化的状态不断压入队列中，直到所有状态都是最优的。这种算法最坏情况下可以达到 O(n^2) （n为状态种数），一般情况下为 O(n) 。

• 优先队列( Dijkstra )

我们只要满足每一次都从状态队列中取出最小代价的状态，即可满足第一次访问最优性。优先队列可以实现这种操作。时间复杂度 O(n\log_2n) 。

有一种比较形象地解释，我们可以把 BFS 的棋盘看作图，即 Dijkstra 用来解决最短路。把这个图 “拎起来 ”，最初拎着起点，然后找当前最高的且没有被拎过的结点，作为下一次拎起来的结点，如此不断去拎，直到把终点结点拎起来，这样拎就可以找到起点和终点的最短距离。

注意，使用优先队列优化的 BFS 不能处理有负数代价的情况，反例如下：

我们要从 S 走到 T ，第一步就可以找到所谓的最小代价2， A 虽然也在队列中，但是10的代价比2大，因此不会被取出。

但实际上， S 走到 T 的最小代价是-90，路径为 S->A->T ,我们得到了错误的答案。

至此，我们成功跳出了命题人挖给我们的的思维陷阱，没有直接按照题意搜索，而是将题意转化，简化问题，大大降低了代码实现复杂度。（听说直接按照题意 dfs 会炸栈空间，虽然 NOIP 开大栈空间，但是你在跑大样例的时候看到程序报 RE 还找不到哪儿错了，对接下来做题的心态会有很大影响）

update on 2020.2.16. CSP-S 2019 的时候，我的几个同学因为不会开大栈空间 Day1T2 没法测大样例，丢分严重，且影响到 Day2 的发挥。

代码实现

1. BFS +优先队列优化

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
template <typename Tp>
void read(Tp &x){
    char c=getchar();x=0;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;
}//快速读入，不解释
struct node{
    int x,y,c,w; 
    bool operator <(node b)const{//const不可丢 
        return w>b.w;
    }//因为STL中优先队列默认取出最大的元素 
     //所以这里重载运算符，保证每次取出的是最小代价的 
};
priority_queue<node>q;//node类型必须定义< 
int dx[]={0,1,0,-1,1,1,-1,-1,0,2,0,-2};//12方向及魔法代价 
int dy[]={1,0,-1,0,1,-1,1,-1,2,0,-2,0};
int dw[]={0,0,0,0,2,2,2,2,2,2,2,2};
int a[105][105],dis[105][105];//a存储棋盘上格子的颜色 
int n,m;
void bfs(){
    memset(dis,0x3f,sizeof(dis));dis[1][1]=0;
    q.push((node){1,1,a[1][1],dis[1][1]});
    node cur,nxt;
    while(!q.empty()){
        cur=q.top();q.pop();
        if(dis[cur.x][cur.y]<cur.w)continue;
        for(int i=0;i<12;i++){//懒惰删除 
            nxt.x=cur.x+dx[i];
            nxt.y=cur.y+dy[i];
            nxt.w=cur.w+dw[i];
            if(nxt.x<=0||nxt.x>m||nxt.y<=0||nxt.y>m)continue;//保证在棋盘范围内
            nxt.c=a[nxt.x][nxt.y];
            if(!nxt.c)continue;
            if(cur.c!=nxt.c)nxt.w++;//确定下一步的信息 
            if(dis[nxt.x][nxt.y]>nxt.w){
                dis[nxt.x][nxt.y]=nxt.w;
                q.push(nxt);
            }
        }
    }
}
int main(){
    int x,y,c;
    read(m);read(n);
    for(int i=1;i<=n;i++){
        read(x);read(y);read(c);
        a[x][y]=c+1;
    }//这里c+1，为了方便区分无色格子 
    bfs();
    if(!a[m][m]){//处理(m,m)无色情况 
        int ans=min(dis[m][m-1],dis[m-1][m])+2;
        if(ans>=inf)puts("-1");
        else printf("%d\n",ans);
    }
    else{
        if(dis[m][m]==inf)puts("-1");
        else printf("%d\n",dis[m][m]);
    }
    return 0;
}

2. 最短路（ Dijkstra ）

注：下面的参考程序使用 zkw线段树 代替优先队列， zkw线段树 短小精悍，常数较小，并且支持直接单点修改，不需要优先队列的懒惰删除法。

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxm 2000005
#define inf 0x3f3f3f3f
template <typename Tp>
void read(Tp &x){
    char c=getchar();x=0;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;
}//快速读入，不解释 
struct Edge{
    int f,t,w,nxt;
}edge[maxm];
int head[maxn],etot=1;//这里有一个小技巧，存图时边数初值设为一个奇数 
void add_edge(int f,int t,int w){//这样可以利用位运算成对变化找到反向边 
    edge[++etot]=(Edge){f,t,w,head[f]};
    head[f]=etot;
}//链式前向星存图 
//--------以下内容为 zkw线段树
//主要思路，用线段树维护dis
//dis1数组表示在线段树中的dis
//tr数组记录当前最小dis对应的节点编号 
//有关zkw线段树，可以参考洛谷日报的讲解，这里不多说 
int tr[maxn<<2],dis1[maxn<<2],bt;
int n,m,S,T;
void build(){
    for(bt=1;bt<=n+1;bt<<=1);//bt初始化，zkw线段树的初始操作 
    for(int i=1;i<=n;i++)tr[i+bt]=i;//tr数组初始化 
    memset(dis1,0x3f,sizeof(dis1));//dis1数组初始化 
    //因为这里dis初值都是inf，所以可以这样直接赋值 
}
void modify(int x,int val){
    dis1[x]=val;x+=bt;//单点修改 
    for(x>>=1;x;x>>=1){//以下是zkw线段树常规操作 
        if(dis1[tr[x<<1]]<dis1[tr[(x<<1)|1]])tr[x]=tr[x<<1];
        else tr[x]=tr[(x<<1)|1];
    }
}//其实上面的内容并不是很长，只是注释比较多 
int dis[maxn];
void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    build();//build()不可忘 
    dis[S]=0;modify(S,0);//源点更新 
    int x,y,w;
    for(int j=1;j<=n;j++){//这里tr[1]维护的是[1,n]dis的最小值的节点编号，所以直接调用 
        x=tr[1];modify(x,inf);//这里将x设为极大值，来取代删除操作 
        for(int i=head[x];i;i=edge[i].nxt){
            y=edge[i].t;w=edge[i].w;
            if(dis[y]>dis[x]+w){//dijkstra松弛操作 
                dis[y]=dis[x]+w;
                modify(y,dis[y]);//直接更新 
            }
        }
    }
}
int dx[]={0,1,0,-1,1,1,-1,-1,0,2,0,-2};//12方向及魔法代价 
int dy[]={1,0,-1,0,1,-1,1,-1,2,0,-2,0};
int dw[]={0,0,0,0,2,2,2,2,2,2,2,2};
int a[105][105],cnt[105][105];
struct node{
    int x,y,c;
}b[maxn];
//a存储棋盘上格子的颜色 
//cnt表示棋盘上的格子对应的节点编号 
void preprocess(){//建图 
    int x,y,c,xx,yy,ww;
    for(int i=1;i<=n;i++){
        x=b[i].x;y=b[i].y;c=b[i].c;
        for(int j=0;j<12;j++){
            xx=x+dx[j];yy=y+dy[j];ww=dw[j];
            if(a[xx][yy]){
                if(a[xx][yy]!=c)ww++;
                add_edge(i,cnt[xx][yy],ww);
            }
        }
    }//这一段在上文题解中讲的比较详细，这里不再多说 
    S=cnt[1][1];
}
int main(){
    int mm,x,y,c;
    read(mm);read(n);
    for(int i=1;i<=n;i++){
        read(x);read(y);read(c);
        a[x][y]=c+1;cnt[x][y]=i;
        b[i]=(node){x,y,c+1};
    }//这里c+1，为了方便区分无色格子 
    preprocess();
    dijkstra();//因为在图论中m常代表的含义是边数 
    if(!a[mm][mm]){//所以用mm取代原题目中的m，即棋盘大小 
        int ans=min(dis[cnt[mm][mm-1]],dis[cnt[mm-1][mm]])+2;
        if(ans>=inf)puts("-1");
        else printf("%d\n",ans);
    }//(m,m)没有颜色的特判 
    else{
        if(dis[cnt[mm][mm]]==inf)puts("-1");
        else printf("%d\n",dis[cnt[mm][mm]]);
    }
    return 0;
}

附：卡掉本题 dfs +记忆化优化(即 SPFA )的做法：数据范围修改为 m\le 1000,n\le 100000 ，因为本题是棋盘，本身就是一种类似于网格图的东西，再加一些比较靠近的有色格子（只能说接近菊花图，因为这一题一个点出度最多为12），再加一些链状有色格子（次优解长链），理论上来讲大部分可以卡掉了。