题解：P3956 [NOIP2017 普及组] 棋盘

dxzier · 2024-08-14 04:11:48 · 题解

本篇题解思想部分来自于 NOIWC2024 第二课堂《最短路算法及其应用》。感谢 “北京大学附属中学 肖然”老师的讲解。

首先在阅读题目后我们可以得知，本题是在一个 m \times m 的棋盘中，每个格子有 0,1, 空 三种情况，每次移动可以向上下左右四个方向移动一格，任意时刻所处的格子不能为空。每走一步：

• 如果出发和到达的格子颜色相同，代价为 0。

• 如果出发和到达的格子颜色不同，代价为 1。

• 可以暂时改变空为 0,1 中的任意一种，代价为 2，不能连续使用。

求从 (1,1) 走到 (m,m) 的最小代价。

容易构造出下图，假设当前所处的点为 0，其中一步就能到达的点为 1，两步才能到达的点为 2。

|||2||| |:-:|:-:|:-:|:-:|:-:| ||2|1|2|| |2|1|0|1|2| ||2|1|2|| |||2|||

对于每一个不为空的点，我们可以按照如下方法建图：

• 如果在标记为 1 的地方存在点，则由标记为 0 的点向此点连边即可，边权由颜色异同决定。

• 如果在标记为 2 的地方存在点，行走过程为先由标记为 0 的点走向标记为 1 的点，再走向标记为 2 的点，但可以直接连接一条从标记为 0 的点到此点的边，边权由颜色异同决定后再加二。

• 对于标记为 1 的点，如果它为空，但坐标却为 (m,m)，可以连接一条由标记为 0 的点向此点，边权为二的边。容易发现仅当该点处在标记为 0 的点的下方或右方时，此点才有可能是 (m,m)。

• 对于标记为 2 的点，如果它为空，但坐标却为 (m,m)，容易发现无法直接到达，因为无法连续改变点的颜色。

在第二条中，如果中间经过的标记为 1 的点不为空，这条由标记为 0 的点直接连向标记为 2 的点的边的边权大于等于二。而先由标记为 0 的点走向标记为 1 的点，再走向标记为 2 的点，这两条边的边权之和小于等于二。所以这样的非法连边在结果上一定不会更优，也就无需对此类非法边进行判断。

建图后在图上跑最短路即可。如果无法到达 (m,m) 则输出 -1。

上述内容与其它题解无异。诚然，这是一道普及组的题目，但在更大的数据范围中，原解法是否仍有一些优化的空间？

稀疏矩阵存储

首先是点的存储问题。在最初的做法中，由于 m \le 100，我们可以使用二维数组存储整个棋盘，然后对其中每一个非空点做上述的建图操作即可。这会使我们的空间复杂度达到 m^2。而如果不使用二维数组，直接判断两点曼哈顿距离，则会使时间复杂度达到 n^2。但当 n,m 扩大到很大却处于同一数量级时，容易发现二维数组中仅有极少一部分点是真正有用的。

对于这种稀疏矩阵的存储，容易想到使用一些数据结构，比如 std::unordered_map。我们可以创建如下对象来存储棋盘中的有效点。

std::unordered_map<int,unordered_map<int,int>> M;

这样我们可以得到一个常数稍大的二维数组，但其平均时空复杂度仍然是 O(n) 的。

特殊条件下的线性单源最短路

0/1 BFS

让我们重新审视单源最短路问题。首先考虑一种特殊情况，边权只有 0/1 两种取值。对于这样的图在 BFS 时可以使用两个队列，每次取两个队列队头中已经过长度 dis 较小的一个元素。对于此点连向的还没遍历过的点，如果边权为 0 则加入第零个队列，如果边权为 1 则加入第一个队列。

若保证队列零中每个元素 dis 相同，队列一队头元素的 dis 大于等于队列零队头元素的 dis，且队列一中每个元素 dis 单调不递减且最多比两队列队头中较小的那个大一。

• 一个元素被插入队列一，其 dis 仅比此时队头中 dis 较小的那个大一，则新插入队列一的元素可以保证队列一仍然具有原性质，则此时原有三项性质均不变。

• 一个元素被插入队列零，若来自队列零则原有三项性质均不变。

• 一个元素被插入队列零，若来自队列一，则队列一队头元素 dis 与队列零队头元素 dis 相同，或队列零为空。对于两种子情况原有三项性质均不变。

• 初始情况下两队列均为空，向任意队列加入初始元素，均具有上述三项性质。

综上所述，该方法可以保证每次取到元素的 dis 单调不递减，所以该方法可以处理边权仅有 0/1 的图上的单源最短路问题。

1/2 BFS

对于这样的图同样可以在 BFS 时可以使用两个队列，每次取两个队列队头中已经过长度 dis 较小的一个元素。对于此点连向的还没遍历过的点，如果边权为 1 则加入第一个队列，如果边权为 2 则加入第二个队列。

此时证明甚至更加简单，仅有两条性质：

队列一中每个元素 dis 单调不递减且最多比两队列队头中较小的那个大一，且队列二中每个元素 dis 单调不递减且最多比两队列队头中较小的那个大二。

仅需同理证明如上两条性质时刻成立，即可保证每次取到元素的 dis 单调不递减，所以该方法可以处理边权仅有 1/2 的图上的单源最短路问题。证明过程不再赘述。

a/b BFS a,b>0 且 a \neq b

与 1/2 BFS 类似，证明如下两条性质时刻成立：

队列一中每个元素 dis 单调不递减且最多比两队列队头中较小的那个大 a，且队列二中每个元素 dis 单调不递减且最多比两队列队头中较小的那个大 b。

由于两条性质时刻成立，可以保证每次取到元素的 dis 单调不递减，所以该方法可以处理边权仅有 a/b 的图上的单源最短路问题。证明过程同样不再赘述。

多边权 BFS

从上面的思考容易想到可以对每一种边权建立一个队列，容易证明过程中对于任意一个队列 i 均保持队列中每个元素 dis 单调不递减且最多比任意一个队列队头中最小的那个大 i。

假设有 k 种不同边权，每次选出其中队头元素的 dis 最小的一个则需要 O(k) 的时间复杂度。当 k 很小，且与题目输入无关时，我们可以不计入复杂度将其看作常数。所以当 k 足够小时，我们可以认为此时最短路算法为线性。（参考“南京外国语学校 杨敏行”《浅谈复杂度及其在解决问题方面的应用》）

但当 k 很大时，这样的做法显然是不优的，于是可以想到用优先队列维护每个队列队头的元素。此时发现代码太过复杂，于是再简化一下代码，把所有元素全部丢进优先队列！于是！我们惊奇的发现！我们重新发明了 Dijkstra 算法！

（（肖老师：早生五十年，你也能发明这些算法。

根据上述所有内容，可以发现此题中当 n,m 扩大到很大却处于同一数量级时棋盘为稀疏矩阵，且仅出现边权 0/1/2/3，于是可以线性解决。

#include <cstdio>
#include <vector>
#include <queue>
#include <unordered_map>
using std::unordered_map;
struct edge{
    int U,V,W;
};
struct point{
    int id,W;
};

int n=0,m=0;
int s=0,t=0;

unordered_map<int,unordered_map<int,int>> M;
unordered_map<int,std::vector<edge>> v;
void add(int s1,int s2,int w0){
    int id1=s1>>1,c1=(s1&1);
    int id2=s2>>1,c2=(s2&1);
    if(!(s2==t&&t==0)){
        if(c1!=c2)
            w0++;
    }
    (v[id1]).push_back({id1,id2,w0});
    return;
}
void buildmap(){
    unordered_map<int,unordered_map<int,int>>::iterator it1=M.begin();
    while(it1!=M.end()){
        unordered_map<int,int>::iterator it2=(it1->second).begin();
        while(it2!=(it1->second).end()){
            int x=it1->first,y=it2->first;

            unordered_map<int,unordered_map<int,int>>::iterator i1=M.find(x-1);
            unordered_map<int,unordered_map<int,int>>::iterator i2=M.find(x);
            unordered_map<int,unordered_map<int,int>>::iterator i3=i2;
            unordered_map<int,unordered_map<int,int>>::iterator i4=M.find(x+1);
            //x-1,y
            if(i1!=M.end()){
                unordered_map<int,int>::iterator in0=(i1->second).find(y);
                if(in0!=(i1->second).end())
                    add(it2->second,in0->second,0);
            }
            //x,y-1
            if(i2!=M.end()){
                unordered_map<int,int>::iterator in0=(i2->second).find(y-1);
                if(in0!=(i2->second).end())
                    add(it2->second,in0->second,0);
            }
            //x,y+1
            if(i3!=M.end()){
                unordered_map<int,int>::iterator in0=(i3->second).find(y+1);
                if(in0!=(i3->second).end())
                    add(it2->second,in0->second,0);
                else if(x==m&&(y+1)==m)
                    add(it2->second,t,2);
            }
            //x+1,y
            if(i4!=M.end()){
                unordered_map<int,int>::iterator in0=(i4->second).find(y);
                if(in0!=(i4->second).end())
                    add(it2->second,in0->second,0);
                else if((x+1)==m&&y==m)
                    add(it2->second,t,2);
            }
            else if((x+1)==m&&y==m)
                add(it2->second,t,2);

            unordered_map<int,unordered_map<int,int>>::iterator i21=M.find(x-2);
            unordered_map<int,unordered_map<int,int>>::iterator i22=M.find(x-1);
            unordered_map<int,unordered_map<int,int>>::iterator i23=i22;
            unordered_map<int,unordered_map<int,int>>::iterator i24=M.find(x);
            unordered_map<int,unordered_map<int,int>>::iterator i25=i24;
            unordered_map<int,unordered_map<int,int>>::iterator i26=M.find(x+1);
            unordered_map<int,unordered_map<int,int>>::iterator i27=i26;
            unordered_map<int,unordered_map<int,int>>::iterator i28=M.find(x+2);
            //x-2,y
            if(i21!=M.end()){
                unordered_map<int,int>::iterator in0=(i21->second).find(y);
                if(in0!=(i21->second).end())
                    add(it2->second,in0->second,2);
            }
            //x-1,y-1
            if(i22!=M.end()){
                unordered_map<int,int>::iterator in0=(i22->second).find(y-1);
                if(in0!=(i22->second).end())
                    add(it2->second,in0->second,2);
            }
            //x-1,y+1
            if(i23!=M.end()){
                unordered_map<int,int>::iterator in0=(i23->second).find(y+1);
                if(in0!=(i23->second).end())
                    add(it2->second,in0->second,2);
            }
            //x,y-2
            if(i24!=M.end()){
                unordered_map<int,int>::iterator in0=(i24->second).find(y-2);
                if(in0!=(i24->second).end())
                    add(it2->second,in0->second,2);
            }
            //x,y+2
            if(i25!=M.end()){
                unordered_map<int,int>::iterator in0=(i25->second).find(y+2);
                if(in0!=(i25->second).end())
                    add(it2->second,in0->second,2);
            }
            //x+1,y-1
            if(i26!=M.end()){
                unordered_map<int,int>::iterator in0=(i26->second).find(y-1);
                if(in0!=(i26->second).end())
                    add(it2->second,in0->second,2);
            }
            //x+1,y+1
            if(i27!=M.end()){
                unordered_map<int,int>::iterator in0=(i27->second).find(y+1);
                if(in0!=(i27->second).end())
                    add(it2->second,in0->second,2);
            }
            //x+2,y
            if(i28!=M.end()){
                unordered_map<int,int>::iterator in0=(i28->second).find(y);
                if(in0!=(i28->second).end())
                    add(it2->second,in0->second,2);
            }
            it2++;
        }
        it1++;
    }
    return;
}

std::vector<int> h;
std::queue<point> q[4];
point getq(){
    int j=-1;
    point ret={-1,2147483647};
    for(int i=0;i<=3;i++){
        if(!q[i].empty()){
            point f=q[i].front();
            if(f.W<ret.W){
                ret=f;
                j=i;
            }
        }
    }
    if(j==-1) return {-1,0};
    q[j].pop();
    return ret;
}
long long BFS(){
    long long ans=-1;
    q[0].push({s,0});
    while(1){
        point tp=getq();
        if(tp.id==t){
            ans=tp.W;
            break;
        }
        if(tp.id<0) break;
        if(h[tp.id]!=0) continue;
        h[tp.id]=1;
        unordered_map<int,std::vector<edge>>::iterator v0=v.find(tp.id);
        if(v0!=v.end()){
            for(int i=0;i<(v0->second).size();i++){
                edge tedge=(v0->second)[i];
                q[tedge.W].push({tedge.V,tp.W+tedge.W});
            }
        }
    }
    return ans;
}

int main(){
    scanf("%d%d",&m,&n);
    h.push_back(0);
    for(int i=1;i<=n;i++){
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        (M[x])[y]=(i<<1)+c;
        h.push_back(0);
        if(x==1&&y==1) s=i;
        if(x==m&&y==m) t=i;
    }
    buildmap();
    printf("%lld",BFS());
    return 0;
}