绝顶我为峰 的妙妙屋

绝顶我为峰 的妙妙屋

海到无边天作岸,山登绝顶我为峰!

题解 P3956 【棋盘】

posted on 2019-02-12 18:57:32 | under 题解 |

很早以前就用$DFSAC$此题,现在老师讲图论留这道题作业,就又来写了一下

本题采用玄学邻接表存边大fa♂法+$Dijkstra$

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int INF = 0x3fffffff;
const int MAX_M = 109;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int m;                   // 棋盘宽度
int chart[MAX_M][MAX_M]; // 棋盘颜色(0/1/2)
int dis[MAX_M][MAX_M];   // 每个格子记作一个节点。由于格子是二维的,所以这里用二维数组比较方便。
                         // 思考:如果要使用一维数组,这里的数组大小应该是多少?下面的程序该如何修改?

struct edge_t {
    int x, y;   // 边的终点
    int weight; // 边的权值

    edge_t(int x_, int y_, int weight_):
        x(x_), y(y_), weight(weight_) { }
};

// priority_queue所需要的辅助类型
struct queue_element {
    int x, y;
    int dis_value;

    queue_element(int x_, int y_, int dis_value_):
        x(x_), y(y_), dis_value(dis_value_) { }

    bool operator <(const queue_element &other) const {
        return dis_value > other.dis_value;
    }
};

vector<edge_t> edges[MAX_M][MAX_M]; // 临接表

// 判断坐标是否在棋盘内
bool xy_valid(int x, int y) {
    return 1<=x && x<=m && 1<=y && y<=m;
}

// 增加一条 (x0,y0) ~> (x1,y1) 权值为weight的边
void add_edge(int x0, int y0, int x1, int y1, int weight) {
    edges[x0][y0].push_back(edge_t(x1, y1, weight));
}

// 添加 (x,y) 连到它的邻居们的边
void add_neighbors(int x, int y) {
    if (chart[x][y] == 0) {
        return;
    }

    for (int i=0; i<4; ++i) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (!xy_valid(tx, ty)) {
            continue;
        }

        if (chart[tx][ty] != 0) {
            // 相邻点
            add_edge(x, y, tx, ty, chart[x][y]==chart[tx][ty] ?0 :1);
            continue;
        }

        for (int j=0; j<4; ++j) {
            int ux = tx + dx[j];
            int uy = ty + dy[j];
            if (!xy_valid(ux, uy) || (x==ux && y==uy) || chart[ux][uy] == 0) {
                continue;
            }

            // 相邻点的相邻点
            add_edge(x, y, ux, uy, chart[x][y]==chart[ux][uy] ?2 :3);
        }
    }
}

// 模板
void dijkstra() {
    priority_queue<queue_element> q;
    q.push(queue_element(1, 1, 0));
    for (int i=1; i<=m; ++i) {
        for (int j=1; j<=m; ++j) {
            dis[i][j] = INF;
        }
    }

    while (!q.empty()) {
        queue_element t = q.top();
        q.pop();
        if (dis[t.x][t.y] != INF) {
            continue;
        }
        dis[t.x][t.y] = t.dis_value;

        for (vector<edge_t>::const_iterator e = edges[t.x][t.y].begin(); e != edges[t.x][t.y].end(); ++e) {
            q.push(queue_element(e->x, e->y, t.dis_value + e->weight));
        }
    }
}

int main() {
    // 输入
    int n; 
    cin >>m >>n;
    for (int i=0; i<n; ++i) {
        int x, y, c;
        cin >>x >>y >>c;
        chart[x][y] = c+1;
    }

    // 思考:
    // chart[m][m]==0时会有什么问题?
    // 为什么下面这样做可以解决?
    // 还可以怎样解决?
    ++m;
    chart[m-1][m] = 1;
    chart[m][m-1] = 2;

    // 建图
    for (int i=1; i<=m; ++i) {
        for (int j=1; j<=m; ++j) {
            add_neighbors(i, j);
        }
    }

    // 求到(1,1)的最短路径
    dijkstra();

    // 输出
    int ans = min(dis[m-1][m], dis[m][m-1]);
    cout <<(ans==INF ?-1 :ans) <<endl;
}

我知道有些地方很神奇

所以下面我来讲解一下

Dijkstra太基础了就不讲了吧

1.代码实现

邻接表&$vector$

顾名思义,一个点后面跟着一大坨个链表用来存边

显然这需要用到链表

但是手打好麻烦呀

于是我们发现 $STL$ 有一个叫做$list$的东西

不用手打链表

但是这玩意儿实在是太鸡肋了

而恰好我们又有更好使的数据结构

所以我们依然不用他

C++真是一门难学的语言

那么,我们用什么呢?

有请大魔王出场!【掌声】

这个东西叫vector蛤?前向星是什么

关于他的介绍很多

在这里不再赘述

拿他就可以实现$list$所有基本操作(复杂度不管

优化$Dijkstra$

众所周知

$Dijkstra$复杂度为$O(N^2)$

而且是实打实的$O(N^2)$

那么$n$巨大无比怎么办?

相信大家都知道$STL$里有个东西叫做$queue$

虽然queue也可以用vector代替

但是这里面有一个逆天的东西叫做$priority\_queue$(优先队列)

这个东西是真的好用,自动排序

用它来优化$Dijkstra$再合适不过啦

但是这个玩意也有他不友善的一面,不支持在线修改

使用$dis$数组维护集合,更新最小值,可以找到元素直接修改

但是你把它扔进$priority\_queue$,当场歇菜

你都找不到这个元素

那怎么办呢?

C++真是一门难学的语言

我们不管他,照旧扔新元素进去,但是要多开一个数组标记这个东西吐没吐出来,如果下一会吐出来了已经吐过的直接扔掉就行了

说到这里,我们发现知道距离的同时,还要知道节点编号,这意味着我们扔给$priority\_queue$的应该是一组数据

有的大佬说:用$pair$

但是打完程序大概是这个样:

xxx.first...xxx.second
xxx.first
xxx.second
xxx.first
xxx.first
xxx.second
xxx.first...xxx.second

W T F ?

鬼知道fist和second是什么东西呀

所以我们不用$pair$

自己写结构体

struct queue_element
{
    int x,y,dis_value;
    queue_element(int x_,int y_,int dis_value_):
        x(x_),y(y_),dis_value(dis_value_){}//赋值,没有为什么,背过
};

C++真是一门难学的语言

然后我们发现$priority\_queue$不认这玩意

他不会比较

我们要重载 $<$(不做注释,自行理解)

bool operator < (const queue_element &other) const
    {
        return dis_value>other.dis_value;
    }

然后就没问题了

2.存边思想

这是一个格子图,怎么把它转化成普通图呢

不难想到用格子做点,相邻格子同色边权为0,异色边权为1,无色不连边

但是,膜♂魔法怎么办?

考虑到魔法用完以后就会消失,相当于耗费2或3金币走两步。那么对于刚才没有连边的格子,将与无色格子相邻的有色格子与当前格子连边,同色边权为2,异色边权为3

接下来又有一个问题,如果终点无色,那么他就不会被连边,那么永远也无法到这个点,所以要预处理,把$m+1$,然后把终点右边、下边的格子分别涂成红色、黄色,就OK了

然后爱咋搞咋搞

主要就是这些了

纯代码

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=0x3fffffff;
const int MAX_M=109;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
int m;
int dis[MAX_M][MAX_M];
int chart[MAX_M][MAX_M];
struct edge_t
{
    int x,y,weight;
    edge_t(int x_,int y_,int weight_):
        x(x_),y(y_),weight(weight_){}
};
struct queue_element
{
    int x,y,dis_value;
    queue_element(int x_,int y_,int dis_value_):
        x(x_),y(y_),dis_value(dis_value_){}
    bool operator < (const queue_element &other) const
    {
        return dis_value>other.dis_value;
    }
};
vector<edge_t> edges[MAX_M][MAX_M];
bool xy_valid(int x,int y)
{
    return 1<=x&&x<=m&&1<=y&&y<=m;
}
void add_edge(int x0,int y0,int x1,int y1,int weight)
{
    edges[x0][y0].push_back(edge_t(x1,y1,weight));
}
void add_neighbors(int x,int y)
{
    if(chart[x][y]==0)
        return;
    for(int i=0;i<4;++i)
    {
        int tx=x+dx[i],ty=y+dy[i];
        if(!xy_valid(tx,ty))
            continue;
        if(chart[tx][ty]!=0)
        {
            add_edge(x,y,tx,ty,chart[x][y]==chart[tx][ty]?0:1);
            continue;
        }
        for(int j=0;j<4;++j)
        {
            int ux=tx+dx[j],uy=ty+dy[j];
            if(!xy_valid(ux,uy)||(ux==x&&uy==y)||chart[ux][uy]==0)
                continue;
            add_edge(x,y,ux,uy,chart[x][y]==chart[ux][uy]?2:3);
        }
    }
}
void dijkstra()
{
    priority_queue<queue_element> q;
    q.push(queue_element(1,1,0));
    for(int i=1;i<=m;++i)
        for(int j=1;j<=m;++j)
            dis[i][j]=INF;
    while(!q.empty())
    {
        queue_element t=q.top();
        q.pop();
        if(dis[t.x][t.y]!=INF)
            continue;
        dis[t.x][t.y]=t.dis_value;
        for(vector<edge_t>::const_iterator e=edges[t.x][t.y].begin();e!=edges[t.x][t.y].end();++e)
            q.push(queue_element(e->x,e->y,t.dis_value+e->weight));
    }
}
int main()
{
    int n;
    cin>>m>>n;
    for(int i=0;i<n;++i)
    {
        int x,y,c;
        cin>>x>>y>>c;
        chart[x][y]=c+1;
    }
    ++m;
    chart[m-1][m]=1;
    chart[m][m-1]=2;
    for(int i=1;i<=m;++i)
        for(int j=1;j<=m;++j)
            add_neighbors(i,j);
    dijkstra();
    int ans=min(dis[m-1][m],dis[m][m-1]);
    cout<<(ans==INF?-1:ans)<<'\n';
    return 0;
}

再见