P3956 [NOIP2017 普及组] 棋盘

原题链接

题解

dijkstra算法的应用。相同颜色权值为0；不同颜色权值为1；有颜色到无颜色权值为2。其中不能连续两步走无颜色结点，即该情况需要特别考虑。

code

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e9;
int a[105][105],dis[105][105],vis[105][105];
int to[5]= {-1,0,1,0,-1},m,n;
struct Node {
    int idx,idy,value;
    bool operator >(const Node &a)const {
        return value>a.value;
    }
};
priority_queue<Node,vector<Node>,greater<Node> > que;
void build(int m) {
    for (int i=1; i<=m; i++)
        for (int j=1; j<=m; j++) {
            a[i][j]=0;
            vis[i][j]=0;
            dis[i][j]=MAX;
        }
}
void Push(Node x,int color,int k) {
    for (int i=0; i<4; i++) {
        Node y;
        y.idx=x.idx+to[i];
        y.idy=x.idy+to[i+1];
        if (x.idx+to[i]>=1 && x.idx+to[i]<=m)
            if (x.idy+to[i+1]>=1 && x.idy+to[i+1]<=m)
                if (vis[x.idx+to[i]][x.idy+to[i+1]]==0) {
                    if (color==1) {
                        if (a[y.idx][y.idy]==0 && k==0 && x.value+2<dis[y.idx][y.idy]) {
                            dis[y.idx][y.idy]=x.value+2;
                            y.value=x.value+2;
                            Push(y,color,k+1);
                        }
                        if (a[y.idx][y.idy]==1 && x.value<dis[y.idx][y.idy]) {
                            dis[y.idx][y.idy]=x.value;
                            y.value=x.value;
                            que.push(y);
                        }
                        if (a[y.idx][y.idy]==2 && x.value+1<dis[y.idx][y.idy]) {
                            dis[y.idx][y.idy]=x.value+1;
                            y.value=x.value+1;
                            que.push(y);
                        }
                    } else if (color==2) {
                        if (a[y.idx][y.idy]==0 && k==0 && x.value+2<dis[y.idx][y.idy]) {
                            dis[y.idx][y.idy]=x.value+2;
                            y.value=x.value+2;
                            Push(y,color,k+1);
                        }
                        if (a[y.idx][y.idy]==2 && x.value<dis[y.idx][y.idy]) {
                            dis[y.idx][y.idy]=x.value;
                            y.value=x.value;
                            que.push(y);
                        }
                        if (a[y.idx][y.idy]==1 && x.value+1<dis[y.idx][y.idy]) {
                            dis[y.idx][y.idy]=x.value+1;
                            y.value=x.value+1;
                            que.push(y);
                        }
                    }
                }
    }
}
int main() {
    cin>>m>>n;
    build(m);
    for (int i=1; i<=n; i++) {
        int x,y,c;
        cin>>x>>y>>c;
        if (c==0) a[x][y]=1;
        if (c==1) a[x][y]=2;
    }
    Node x;
    bool bol=false;
    x.idx=1;
    x.idy=1;
    x.value=0;
    dis[1][1]=0;
    que.push(x);
    while (!que.empty()) {
        x=que.top();
        que.pop();
        vis[x.idx][x.idy]=1;
        if (x.idx==m && x.idy==m) {
            cout<<dis[m][m]<<endl;
            bol=true;
            break;
        }
        if (dis[x.idx][x.idy]<x.value) continue;
        Push(x,a[x.idx][x.idy],0);
    }
    if (a[m][m]==0 && dis[m][m]!=MAX) cout<<dis[m][m];
    else if (bol==false)cout<<-1<<endl;
    return 0;
}