洛谷 P3956 [NOIP2017 普及组] 棋盘

本文主要是介绍洛谷 P3956 [NOIP2017 普及组] 棋盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：优先队列

其实本来想用双端队列进行解答的，但是呢，题目中有一个比较特殊的地方，那就是可以施展魔法让没有颜色的格子变成有颜色的格子，这样的话你如果普通的按照双端队列那样存储，会得不偿失，因为你将面临两个问题：何时才能涂颜色？涂颜色应该涂什么颜色最好呢？所以pass。

这里看了题解才知道要用优先队列进行优化。先从最折磨人的施展魔法这里讲起吧......

这个魔法问题，我们其实可以转化连续跳两个格子而代价为2的问题。

参照一个大佬的图像来讲解，也就是蓝色的格子就是我们施展魔法之后走到的格子，也就是连续跳2个格子。跳两个格子的含义我们知道了，但是代价为什么是2呢？有没有可能是3呢？不，我们考虑的就是最优情况，也就是说，我们跳这几个格子之后，自认为绿色的格子就是与蓝色的格子相同的颜色。

好，这个问题解决之后，我们需要知道为什么要用优先队列来处理？我们知道，优先队列是对存储的数值的某个属性从大到小排序的，我们这里需要用最小代价，所以可以改正优先队列的排序顺序，让它以最小代价为top。也就是堆的顺序改一下。

OK，这样还没完，终点我们需要特判一下，终点可能没有颜色呢？终点只能由它的上方走来，或者左方走来，那么得判断这两个方位的dist代价值哪一个小了，然后+2，因为需要涂色终点才能走。OK，这样我们需要知道这个时候这个值为多少，如果是大于初始值，那么也就是说到达终点的必经之路都没有涂色，而终点也没有涂色，意味着我们需要连续涂色两次，我们就认为这是不能到达的，魔法不能重复使用。

终点有颜色的情况我们也需要知道，也就是说，如果有颜色但是dist的值还是初始值，证明没有遍历到它，也就是不能到达。

上代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_map>
#include<set>
#define int long long
#define MAX 505
#define inf 0x3f3f3f3f
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts;
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 };//在上下左右的时候，代价手算，如果方块颜色相同，就不变，不同再+1
struct node {int x;int y;int c;//颜色int w;//代价bool operator <(node b)const {return w > b.w;//优先队列因为是把代价从大到小排列的，所以我们需要改变一下，改成从小到大。}
};
priority_queue<node>q;
int maps[MAX][MAX];//存储原先地图里面的颜色
int dist[MAX][MAX];//用来记录每个格子的最优代价
void bfs() {memset(dist, 0x3f, sizeof dist);dist[1][1] = 0;q.push({ 1,1,maps[1][1],dist[1][1] });node d;while (!q.empty()) {auto tmp = q.top();q.pop();if (dist[tmp.x][tmp.y] < tmp.w)//如果说dist已经比现在这个遍历的格子要代价小了continue;_for(i, 0, 12) {//遍历d.x = dx[i] + tmp.x;d.y = dy[i] + tmp.y;d.w = dw[i] + tmp.w;if (d.x > n || d.x < 1 || d.y<1 || d.y>n)//边界处理continue;d.c = maps[d.x][d.y];if (!d.c)//如果说是无色，那就继续（在后面我们把颜色的数值都加了1，这样方便判断无色continue;if (tmp.c != d.c)d.w++;//颜色不同的时候代价+1if (dist[d.x][d.y] > d.w) {dist[d.x][d.y] = d.w;//这个时候遍历的格子是最优解q.push(d);}}}}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n >> m;_for(i, 1, m + 1) {int x;int y;int c;cin >> x >> y >> c;maps[x][y] = c+1;}bfs();if (!maps[n][n]) {//判断最后一个格子是不是有颜色int res = min(dist[n - 1][n], dist[n][n - 1]) + 2;//这里因为if (res >= inf)cout << -1 << endl;elsecout << res << endl;}else {if (dist[n][n] >= inf)//终点没有遍历到，也就是没有到达cout << -1 << endl;elsecout << dist[n][n] << endl;}return 0;
}

这篇关于洛谷 P3956 [NOIP2017 普及组] 棋盘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---