Luogu

算法

我考场上口胡出了这个做法结果没有写

先建图，然后最短路。

建图的话，先考虑周围四个点。颜色相同连0，不同连1。
然后再考虑周围白点周围的点，颜色相同连2，不同连3。
然后跑最短路就行了。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#define re register
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
int INF=0x3f3f3f3f;
int n,m;
int mp[110][110];
int ans=2147483647;
inline void Init() {
    n=read(); m=read();
    for (re int i=1;i<=m;i++) {
        int x=read(),y=read(),c=read();
        mp[x][y]=c+1;
    }
}
struct Edge { int v,w,nxt; } e[1000010];
int head[10010],cnt=0;
inline int H(int x,int y) { return (x-1)*n+y; }
inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int fx[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
inline int Make_Graph() {
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
            if (mp[i][j]==0) continue;
            for (re int k=0;k<4;k++) {
                int x=i+fx[k][0],y=j+fx[k][1];
                if (x<1||x>n||y<1||y>n) continue;
                if (mp[x][y]!=0) addEdge(H(i,j),H(x,y),mp[i][j]!=mp[x][y]);
                else {
                    addEdge(H(i,j),H(x,y),2);
                    for (re int t=0;t<4;t++) {
                        int xx=x+fx[t][0],yy=y+fx[t][1];
                        if (t==(k^1)) continue;
                        if (mp[xx][yy]==0) continue;
                        if (xx<1||xx>n||yy<1||yy>n) continue;
                        addEdge(H(i,j),H(xx,yy),2+(mp[i][j]!=mp[xx][yy]));
                    }
                }
            }
        }
}
struct HeapNode {
    int u,d;
    bool operator <(const HeapNode& rhs) const {
        return d>rhs.d;
    }
};
int dis[10010];
inline void Dijkstra() {
    memset(dis,0x3f3f3f3f,sizeof(dis));
    INF=dis[0]; dis[H(1,1)]=0;
    priority_queue<HeapNode> Q;
    Q.push((HeapNode){H(1,1),0});
    while (!Q.empty()) {
        HeapNode x=Q.top(); Q.pop();
        int u=x.u,d=x.d;
        if (d!=dis[u]) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                Q.push((HeapNode){v,dis[v]});
            }
        }
    }
}
int main() {
    Init(); Make_Graph(); Dijkstra();
    if (dis[H(n,n)]==INF) printf("-1\n");
    else printf("%d\n",dis[H(n,n)]);
    return 0;
}