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

【输入输出样例 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。
查看答案与解析
答案:<p style="text-align: left;">#include <iostream></p><p style="text-align: left;">#include <bits/stdc++.h></p><p style="text-align: left;">#include<set></p><p style="text-align: left;">#include<string.h></p><p style="text-align: left;">#include<algorithm></p><p><br style="text-align: left;"/></p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">// 1 黄 0 红</p><p style="text-align: left;">int dis[4][2]={{-1,0},{1,0},{0,1},{0,-1}};</p><p style="text-align: left;">int n,m;</p><p style="text-align: left;">const int maxn=105;</p><p style="text-align: left;">struct node</p><p style="text-align: left;">{</p><p style="text-align: left;"> int x,y,c,v;</p><p style="text-align: left;">};</p><p style="text-align: left;">queue<node>q;</p><p style="text-align: left;">int yy[maxn][maxn],val[maxn][maxn];</p><p style="text-align: left;">int ans=0x7f7f7f7f;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">void Init()</p><p style="text-align: left;">{</p><p><br style="text-align: left;"/></p><p style="text-align: left;"> memset(yy,-1,sizeof(yy));</p><p style="text-align: left;"> memset(val,0x7f,sizeof(val));</p><p style="text-align: left;">}</p><p style="text-align: left;">void dfs(int x,int y)</p><p style="text-align: left;">{</p><p><br style="text-align: left;"/></p><p style="text-align: left;"> node pq;</p><p style="text-align: left;"> pq.x=x,pq.y=y,pq.c=yy[x][y],pq.v=0;</p><p style="text-align: left;"> val[x][y]=0;</p><p style="text-align: left;"> q.push(pq);</p><p style="text-align: left;"> while(!q.empty())</p><p style="text-align: left;"> {</p><p style="text-align: left;"> node now=q.front();</p><p style="text-align: left;"> if(now.v>ans)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> q.pop();</p><p style="text-align: left;"> continue;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> if(now.x==m&&now.y==m)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> ans=min(ans,now.v);</p><p style="text-align: left;"> q.pop();</p><p style="text-align: left;"> continue;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> for(int i=0;i<4;i++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> int dx=now.x+dis[i][0],dy=now.y+dis[i][1];</p><p style="text-align: left;"> if(dx>0&&dy>0&&dx<=m&&dy<=m)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> int bc=yy[now.x][now.y],dc=yy[dx][dy],mv=val[dx][dy],dv;</p><p style="text-align: left;"> if(bc>=0&&dc>=0)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> dv=now.v+(bc==dc?0:1);</p><p style="text-align: left;"> if(mv>dv)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> q.push((node){dx,dy,dc,dv});</p><p style="text-align: left;"> val[dx][dy]=dv;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> else if(dc<0&&bc>=0)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> dv=now.v+2;</p><p style="text-align: left;"> if(mv>dv)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> q.push((node){dx,dy,bc,dv});</p><p style="text-align: left;"> val[dx][dy]=dv;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> else if(bc<0&&dc>=0)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> dv=now.v+(now.c==dc? 0:1);</p><p style="text-align: left;"> if(mv>dv)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> q.push((node){dx,dy,dc,dv});</p><p style="text-align: left;"> val[dx][dy]=dv;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> q.pop();</p><p style="text-align: left;"> }</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p><br style="text-align: left;"/></p><p style="text-align: left;"> cin>>m>>n;</p><p style="text-align: left;"> Init();</p><p style="text-align: left;"> int x,y,c;</p><p style="text-align: left;"> for(int i=1;i<=n;i++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> cin>>x>>y>>c;</p><p style="text-align: left;"> yy[x][y]=c;</p><p><br style="text-align: left;"/></p><p style="text-align: left;"> }</p><p style="text-align: left;"> dfs(1,1);</p><p style="text-align: left;"> if(ans==0x7f7f7f7f)</p><p style="text-align: left;"> cout<<-1<<endl;</p><p style="text-align: left;"> else</p><p style="text-align: left;"> cout<<ans<<endl;</p><p style="text-align: left;"> return 0;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">}</p>
这道题暂未补解析。