NOIP2017 普及 luogu3956 棋盘

NOIP2017 普及 luogu3956 棋盘

​​ 题目描述 有一个m × m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。 任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1 个金币。 另外， 你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。 现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？ 输入输出格式 输入格式： 数据的第一行包含两个正整数 m， n，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。 接下来的 n 行，每行三个正整数 x， y， c， 分别表示坐标为（ x， y）的格子有颜色 c。 其中 c=1 代表黄色， c=0 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为（ 1, 1），右下角的坐标为（ m, m）。 棋盘上其余的格子都是无色。保证棋盘的左上角，也就是（ 1， 1） 一定是有颜色的。 输出格式： 输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出-1。 输入输出样例 输入样例#1： 复制 5 7 1 1 0 1 2 0 2 2 1 3 3 1 3 4 0 4 4 1 5 5 0 输出样例#1： 复制 8 输入样例#2： 复制 5 5 1 1 0 1 2 0 2 2 1 3 3 1 5 5 0 输出样例#2： 复制 -1 说明 输入输出样例 1 说明

从（ 1， 1）开始，走到（ 1， 2）不花费金币 从（ 1， 2）向下走到（ 2， 2）花费 1 枚金币 从（ 2， 2）施展魔法，将（ 2， 3）变为黄色，花费 2 枚金币 从（ 2， 2）走到（ 2， 3）不花费金币 从（ 2， 3）走到（ 3， 3）不花费金币 从（ 3， 3）走到（ 3， 4）花费 1 枚金币 从（ 3， 4）走到（ 4， 4）花费 1 枚金币 从（ 4， 4）施展魔法，将（ 4， 5）变为黄色，花费 2 枚金币， 从（ 4， 4）走到（ 4， 5）不花费金币 从（ 4， 5）走到（ 5， 5）花费 1 枚金币 共花费 8 枚金币。 输入输出样例 2 说明

从（ 1， 1）走到（ 1， 2），不花费金币 从（ 1， 2）走到（ 2， 2），花费 1 金币 施展魔法将（ 2， 3）变为黄色，并从（ 2， 2）走到（ 2， 3）花费 2 金币 从（ 2， 3）走到（ 3， 3）不花费金币 从（ 3， 3）只能施展魔法到达（ 3， 2），（ 2， 3），（ 3， 4），（ 4， 3） 而从以上四点均无法到达（ 5， 5），故无法到达终点，输出－1 数据规模与约定 对于 30%的数据， 1 ≤ m ≤ 5， 1 ≤ n ≤ 10。 对于 60%的数据， 1 ≤ m ≤ 20， 1 ≤ n ≤ 200。 对于 100%的数据， 1 ≤ m ≤ 100， 1 ≤ n ≤ 1,000。 点这么少 边这么少 但是对于宽搜来说还是数据范围有点大 不妨尝试spfa 然后就是个恶心的建图了 红色就在mp中为0 黄色为1 白色为2 相同建0 不同建1 如果是白色 就考虑多种情况要么是2或3的 我是把每个点拆成三个颜色的点 可能会产生很多废点 不过 对于这么小的数据范围是不成问题的 然后考虑起点是否为白色 然后入队spfa即可

#include#include#include#define N 110#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}struct node{ int x,y,z,next;}data[220000];int flag[33000],f[33000],n,m,mp[110][110],num,h[33000];int dx[]={0,1,0,-1},dy[]={1,0,-1,0};inline int calc(int x,int y,int c){ int tmp=0;tmp+=((x-1)*n+y-1)*3; tmp+=c+1;return tmp;}inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].next=h[x];data[num].z=z;h[x]=num;data[num].x=x;}void spfa(){ memset(f,0x3f,sizeof(f));queueq; if (mp[1][1]==2){ f[1]=2;f[2]=2;flag[1]=flag[2]=1;q.push(1);q.push(2); }else{ f[1+mp[1][1]]=0;flag[1+mp[1][1]]=1;q.push(1+mp[1][1]); } while (!q.empty()){ int x=q.front();q.pop();flag[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (f[x]+zn||y1<1||y1>n) continue; if (mp[x1][y1]==2) continue; insert1(calc(i,j,0),calc(x1,y1,mp[x1][y1]),0!=mp[x1][y1]); insert1(calc(i,j,1),calc(x1,y1,mp[x1][y1]),1!=mp[x1][y1]); } }else{ for (int k=0;k<4;++k){ int x1=i+dx[k],y1=j+dy[k]; if (x1<1||x1>n||y1<1||y1>n) continue; if (mp[x1][y1]==2) { insert1(calc(i,j,mp[i][j]),calc(x1,y1,0),2+(0!=mp[i][j])); insert1(calc(i,j,mp[i][j]),calc(x1,y1,1),2+(1!=mp[i][j])); }else{ insert1(calc(i,j,mp[i][j]),calc(x1,y1,mp[x1][y1]),mp[i][j]!=mp[x1][y1]); } } } } } /*for (int i=1;i<=num;++i){ printf("%d %d %d\n",data[i].x,data[i].y,data[i].z); }*/ spfa();bool flag1=1;int ans=0x3f3f3f3f; for(int i=1;i<=3;++i){ if (f[(n*n-1)*3+i]!=inf) flag1=0,ans=min(ans,f[(n*n-1)*3+i]); } if (flag1) printf("-1");else printf("%d",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。