NOIP2017普及组-棋盘

开始noip得训练主要是因为得到一份兼职工作，给小朋友们讲课=。=

退役了一年多，没碰过算法的老咸鱼为了不误人子弟还是抽时间训练起来吧。

不得不说，中文题真的爽啊，比acm要开心多了。

image

image

说来惭愧。

我的第一反应就是暴搜。。。

然后写着写着发现有点最短路的意思？

用priority_queue记录到每个点用的最少花费，空白点只可能是神奇魔法来的，但是它后面的点必须有颜色。所以我单独开了一个东西记录现在这个点的颜色，而输入的数组不动，以用来看上一步的各自是被魔法来的颜色还是本身就有的。
其他的和dijkstra最短路几乎一样。因为是优先队列，所以每个点进入队列一次就可以，后面来的肯定是花费更多了。（所以我加了num数组，就算不加也不会影响结果，但是会慢一丢丢，毕竟一些没有用的点进到了队列里。）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> pi;
typedef pair<pi,pi> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
const int maxn = 110;
int n,m,t1,t2,t3,a[maxn][maxn];
int vis[maxn][maxn],ans = -1,num[maxn][maxn];
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};

void init(){
    scanf("%d%d",&m,&n);
    for(int i = 0 ; i < n ; i++){
        scanf("%d%d%d",&t1,&t2,&t3);
        a[t1][t2] = t3+1;
    }
}
void sov(){
    q.push(make_pair(make_pair(0,a[1][1]),(make_pair(1,1))));
    memset(vis,-1,sizeof(vis));
    num[1][1] = 1;
    while(!q.empty()){
        pii node = q.top(),node2;
        q.pop();
        int cost = node.first.first;
        int col = node.first.second;
        int x = node.second.first;
        int y = node.second.second;
        if(vis[x][y] != -1 && vis[x][y] > cost) vis[x][y] = cost;
        else if(vis[x][y] == -1)   vis[x][y] =cost;
        else continue;

        for(int i = 0;i < 4; i++){
            int nextx = x+dir[i][0];
            int nexty = y+dir[i][1];
            if(a[x][y] == 0 && a[nextx][nexty] == 0)    continue;
            if(nextx < 1||nexty < 1 || nextx > m || nexty > m||num[nextx][nexty])  continue;
            if(a[nextx][nexty] == 0){
                node2.first.first = cost+2;
                node2.first.second = col;
            }
            else if(a[nextx][nexty] == col){
                node2.first.first = cost;
                node2.first.second = col;
            }
            else{
                node2.first.first = cost+1;
                node2.first.second = a[nextx][nexty];
            }
            node2.second.first = nextx;
            node2.second.second = nexty;
            q.push(node2);

            num[nextx][nexty]++;
        }
    }
    printf("%d\n",vis[m][m]);
}
int main(){
    init();
    sov();
}