题解 P3956 【棋盘】

很早以前就用$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了 ~~然后爱咋搞咋搞~~ ### 主要就是这些了 纯代码 ```cpp #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; } ``` ## 再见