M_sea

洛谷3956 棋盘
题目描述有一个m × m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘...
扫描右侧二维码阅读全文
19
2017/12

洛谷3956 棋盘

题目描述

有一个m × m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。

任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的), 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时,如果两个格子的颜色相同,那你不需要花费金币;如果不同,则你需要花费 1 个金币。

另外, 你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用, 而且这个魔法的持续时间很短,也就是说,如果你使用了这个魔法,走到了这个暂时有颜色的格子上,你就不能继续使用魔法; 只有当你离开这个位置,走到一个本来就有颜色的格子上的时候,你才能继续使用这个魔法,而当你离开了这个位置(施展魔法使得变为有颜色的格子)时,这个格子恢复为无色。

现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少?

传送门

算法

先建图,然后乱搞。。。

建图的话,先考虑周围四个点。颜色相同连0,不同连1。
然后再考虑周围白点周围的点,颜色相同连2,不同连3。

然后Dij/SPFA乱搞。。。

注意点的编号可以Hash一下,更方便。

我考场上为什么没写出来呢。

代码

#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;
}
最后修改:2018 年 11 月 09 日 04 : 34 PM

发表评论

1 条评论

  1. M_sea

    有吗、、、