P3956 [NOIP2017 普及组] 棋盘

分析

首先说可以用dfs写，但是不建议。

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

而且这数据范围，赛中我大概率不敢写DFS，所以我们来看看大佬关于bfs的思路。

ZigZagKmp

这个题目给了我一些启发。

关于一些操作，我们没办法直接在两步内(即转移的那一次)体现出来，我之前的操作往往是写成一个分层图(即加一些状态来区分到达相同点的不同状态)，但这次题目写的时候我发现很难将状态成功分层后连接，大佬的思路给了我其他的启发，我们可以尝试将这个操作转化为能两步中体现出来的

但是，我想说的重点在下边

这题，我是用的Dijkstra写的，中间出现了很多问题，我就挑其中比较重要的说一下

1. 因为每个点的状态，除了坐标外，又新增了一个，上一次是否使用了魔法，以及使用了魔法之后，无颜色的格子变成了什么颜色。

   不难想到，用结构体就好，结构体内存坐标，是否使用魔法，格子的颜色。这里我取了个巧，直接看代码

   struct Node
   {
       int x,y,c,dist;//c=-1时，代表这个格子不是空白格，c=0/1时，则代表空白格子现在是什么格子
       bool operator<(const Node& W)const 
       {
           return dist>W.dist;
       }
   };
   

2. 还有就是给我坑了一个多小时的坑点。转移状态时，分情况讨论一定要清楚，按顺序考虑

   1. 不能两个各自都是空白格
   2. 当前格子是空白格
   3. 下一个格子是空白格

   坑死我了，呜呜呜。我们直接上错误代码，看看怎么犯得蠢

   for(int i=0;i<4;i++)
   {
       int nx = x + dx[i],ny = y + dy[i];
       if(nx<=0||nx>n||ny<=0||ny>n) continue;
       if(g[x][y]!=-1||g[nx][ny]!=-1)
       {
           int color = t.c==-1?g[x][y]:t.c;
           if(g[nx][ny]==-1&&dist[x][y]+2<dist[nx][ny])//这就是一个巨坑
           {
               dist[nx][ny] = dist[x][y] + 2;
               q.push({nx,ny,color,dist[nx][ny]});
           }
           else if(color==g[nx][ny]&&dist[x][y]<dist[nx][ny])
           {
               dist[nx][ny] = dist[x][y];
               q.push({nx,ny,-1,dist[nx][ny]});
           }
           else if(color!=g[nx][ny]&&dist[x][y]+1<dist[nx][ny])
           {
               dist[nx][ny] = dist[x][y] + 1;
               q.push({nx,ny,-1,dist[nx][ny]});
           }
           // st[nx][ny] = 1;
           // if(nx==n&&ny==n) return ;
       }
   }
   

   上方注释出的错误，我们在这里展开谈谈，这个条件代表的意思是什么呢？

   只有下一个节点是空白格，且满足更新条件，就更新

   那不满足的条件有哪些呢？

   下一个节点不是空白格或者不满足更新条件

   这显然不对，因为这个更新条件必须在下一个节点是空白格的时候才会检验

   所以，我们就更改一下就好了

   for(int i=0;i<4;i++)
   {
       int nx = x + dx[i],ny = y + dy[i];
       if(nx<=0||nx>n||ny<=0||ny>n) continue;
       if(g[x][y]!=-1||g[nx][ny]!=-1)
       {
           int color = t.c==-1?g[x][y]:t.c;
           if(g[nx][ny]==-1)
           {
               if(dist[x][y]+2<dist[nx][ny]){
                   dist[nx][ny] = dist[x][y] + 2;
                   q.push({nx,ny,color,dist[nx][ny]});
               }
           }
           else 
           {
               if(color==g[nx][ny]&&dist[x][y]<dist[nx][ny])
               {
                   dist[nx][ny] = dist[x][y];
                   q.push({nx,ny,-1,dist[nx][ny]});
               }
               else if(color!=g[nx][ny]&&dist[x][y]+1<dist[nx][ny])
               {
                   dist[nx][ny] = dist[x][y] + 1;
                   q.push({nx,ny,-1,dist[nx][ny]});
               }
           }
       }
   }
   

但是以上都只是代码实现时候的一些小问题而已，我更想说的是，我看到的一篇题解

题解指路

类似于上边连接中的代码。其实题解中好多人使用的都是这样的写法。把队列简单的换成了优先队列，其他地方没有任何改变

但是没有人讲它为什么对，我看到的时候属实是冲击到我了。

因为看似在Dijkstra和BFS中只是简单的将标志节点的位置换了一下，但是了解这两种算法的人很清楚，这两种算法拥有本质上的不同。

标志数组的含义不同，在Dijkstra中，标志数组st的含义是，当前节点是否已经出队，若出队了，则已经确定最短路。而在BFS中，st数组的含义则变为了，是否已经扫描到该点，若扫描到了，则已经确定最短路。st数组的不同本质上是两种算法的思维不同，同时时间复杂度也是不相同的。

在一般的BFS中，我们能够确定扫描到时，就已经确定最短路，是因为边权都相同，则先扫到时，一定是最短的，后面再扫到的一定比此时长，因此我们可以在扫到的该点是可以直接进行标记。

而在Dijkstra中，我们是利用三角不等式进行不断的更新，只有当此时到达该点的已经是到达其他未确定的点中最短路径的点了，那就可以确定了，此时的路径就是最短的了，此时才能进行标记。

那为什么这里简单的换一下，就是对的了呢？

其实也不难证明，我们来分类讨论一下

假设此时取出的点为i，那从i到的下一个点为k，下面我们假设从队列中取出i之后的点j下一个点也为k，并且dist[j]=dist[i]

1. k为空格子,则两者都+2
2. k不为空格子，不妨设为红色
   1. i和j相同颜色，则改变k时的距离都相同
   2. 而i和j不同颜色，这种情况不会发生。因为其中一定是一奇一偶，可以想想为什么

因此，我们可以证明在这道题中，直接更换不会出现问题。

但若是，改变了魔法的权值呢？那就不对了，因为可以将魔法的代价调的很大，这样就破坏了不会出现的那种情况。

AC_code

#include<bits/stdc++.h>
using namespace std;
#define N 105
int a[N][N],n,ge;
const int wx[5]={0,0,1,-1};
const int wy[5]={1,-1,0,0};
bool b[N][N];
struct edge{
    int xx,yy,money,color;
    bool use;
    friend bool operator <(const edge &xxx,const edge &yyy){
        return xxx.money>yyy.money;
    }
};
void BFS(){
    priority_queue<edge> Q;
    edge e;
    e.xx=e.yy=1,e.money=e.use=0;
    e.color=a[1][1];
    Q.push(e);
    b[1][1]=1;
    while(!Q.empty()){
        edge t;
        t=Q.top();Q.pop();
        for(int i=0;i<4;++i){
            edge news;
            news.xx=t.xx+wx[i],news.yy=t.yy+wy[i];
            if(news.xx<1||news.yy<1||news.xx>n||news.yy>n||b[news.xx][news.yy])
                continue;
            news.use=!t.use;
            if(a[news.xx][news.yy]==0){
                if(news.use)        
                    news.money=t.money+2,news.color=t.color,news.use=1;
                else continue;
            }
            else{
                if(news.use)
                    news.use=0;
                if(a[news.xx][news.yy]==t.color)
                    news.money=t.money,news.color=a[news.xx][news.yy];
                else
                    news.money=t.money+1,news.color=a[news.xx][news.yy];
            }
            b[news.xx][news.yy]=1;
            if(news.xx==n&&news.yy==n){
                printf("%d\n",news.money);
                return;
            }
            Q.push(news);
        }
    }   
    printf("-1\n");
}
int main(){
    int x,y,z;
    scanf("%d%d",&n,&ge);
    for(int i=1;i<=ge;++i){
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=z+1;
    }
    BFS();
    return 0;
}