题解 P3956 【棋盘】

### update on 2020.2.16 看到评论区有同学对排版的建议，故对文章排版进行一些优化，使本题解符合现行题解规范。 ## 写在前面 这是本蒟蒻一年前发的题解，因此有些地方讲的不是特别清楚，代码也比较冗长。其实这一题没有必要将其转换为图论模型，在上面跑最短路，可以直接使用优先队列优化的 `BFS` 。 `NOIP2017`普及组比赛，是我参加的第一次复赛，当时我太菜了（虽然说现在的我也还是很菜），这一题最暴力的 `dfs` 都写不对，不知怎么拿到了`20`分，其余的测试点 `WA`+`TLE` ，在考场上时间几乎全用来氪这一题，结果最后一题想出`50`分 `DP` 没调完，`220`滚粗。考场上主要纠结于如何处理魔法，因此考后和[同学](https://www.luogu.com.cn/user/28910)想到了这样一种代替魔法的算法。 这一次修改，将对原题解中解释的不是很清楚的地方作较为清晰的解释，并且修改了最后的参考程序，提供本题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` +优先队列优化 ```cpp #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线段树` 短小精悍，常数较小，并且支持直接单点修改，不需要优先队列的懒惰删除法。 ```cpp #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$），再加一些链状有色格子（次优解长链），理论上来讲大部分可以卡掉了。