P3956 棋盘的题解。
代码
#include<bits/stdc++.h>
#define pass {}//em...
using namespace std;
struct pos
{
int x,y;
int gd;
int ppx,ppy;
};
queue<pos>q;
int m,n,g[100+1][100+1],v[100+1][100+1]={0};
int xx[]={0,0,0,1,-1};
int yy[]={0,1,-1,0,0};
void bfs()
{
q.push((pos){1,1,0,0,0});
v[1][1]=0;
while(!q.empty())
{
pos tmp=q.front();
q.pop();
int px=tmp.x,py=tmp.y;
for(int i=1;i<=4;i++)
{
int nx=px+xx[i],ny=py+yy[i],ng=tmp.gd;
//***
if(px>=1&&px<=m&&py>=1&&py<=m)
if(g[nx][ny]&&g[px][py])
if(g[nx][ny]!=g[px][py])
ng+=1;
else
pass
else if(g[nx][ny]==0&&g[px][py])
ng+=2;
else if(g[px][py]==0&&g[nx][ny])
if(g[nx][ny]==g[tmp.ppx][tmp.ppy])
pass
else
ng+=1;
else
continue;
else
continue;
//***orz判断
if(ng<v[nx][ny]||v[nx][ny]==-1)
{
q.push((pos){nx,ny,ng,px,py});
v[nx][ny]=ng;
}
}
}
}
int main()
{
read(m),read(n);
for(int i=1;i<=n;i++)
{
int a,b,c;
read(a),read(b),read(c);
g[a][b]=c+1;
}
memset(v,-1,sizeof(v));
bfs();
print(v[m][m]);//CE
return 0;
}
思路
有一个 的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1 个金币。
另外， 你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？
有颜色，还有魔法，看起来很麻烦！
那就要采取步步推进的做题方法了！
step 1(读图)
#include<bits/stdc++.h>
#define pass {}//em...
using namespace std;
struct pos
{
int x,y;
int gd;
};
queue<pos>q;
int m,n,g[100+1][100+1],v[100+1][100+1]={0};
int xx[]={0,0,0,1,-1};
int yy[]={0,1,-1,0,0};
int main()
{
read(m),read(n);
for(int i=1;i<=n;i++)
{
int a,b,c;
read(a),read(b),read(c);
g[a][b]=c+1;
}
memset(v,-1,sizeof(v));
return 0;
}
g[][]数组存图，0表示啥也没有，1表示红色，2表示黄色。
v[][]标记数组，-1表示未访问，否则就是到达这个点所花费的金币数。
xx[] yy[]模拟了坐标的位移。
在pos结构体中，x,y记录坐标，gd记录到达这个点所花费的最少金币数。
step 2(无魔法)
#include<bits/stdc++.h>
#define pass {}//em...
using namespace std;
struct pos
{
int x,y;
int gd;
};
queue<pos>q;
int m,n,g[100+1][100+1],v[100+1][100+1]={0};
int xx[]={0,0,0,1,-1};
int yy[]={0,1,-1,0,0};
void bfs()
{
q.push((pos){1,1,0});
v[1][1]=0;
while(!q.empty())
{
pos tmp=q.front();
q.pop();
int px=tmp.x,py=tmp.y;
for(int i=1;i<=4;i++)
{
int nx=px+xx[i],ny=py+yy[i],ng=tmp.gd;
//***
if(px>=1&&px<=m&&py>=1&&py<=m)
if(g[nx][ny]&&g[px][py])
if(g[nx][ny]!=g[px][py])
ng+=1;
else
pass
else
continue;
else
continue;
//***orz判断
if(ng<v[nx][ny]||v[nx][ny]==-1)
{
q.push((pos){nx,ny,ng});
v[nx][ny]=ng;
}
}
}
}
int main()
{
read(m),read(n);
for(int i=1;i<=n;i++)
{
int a,b,c;
read(a),read(b),read(c);
g[a][b]=c+1;
}
memset(v,-1,sizeof(v));
bfs();
print(v[m][m]);//CE
return 0;
}
魔法过于复杂，先不考虑。先只考虑颜色的问题。
其实最核心的代码是那一堆判断。
if(px>=1&&px<=m&&py>=1&&py<=m)
if(g[nx][ny]&&g[px][py])
if(g[nx][ny]!=g[px][py])
ng+=1;
else
pass
else
continue;
else
continue;
line 1：越界判断
line 2：是否两者都有颜色
line 3：若是，那颜色是否不相同
line 4：若是，花费1金币
line 5,6：否则，啥也不干
就这么简单！
if(ng<v[nx][ny]||v[nx][ny]==-1)
{
q.push((pos){nx,ny,ng});
v[nx][ny]=ng;
}
line 1：取最优
line 3,4：压入队列！
step 3(end)
#include<bits/stdc++.h>
#define pass {}//em...
using namespace std;
struct pos
{
int x,y;
int gd;
int ppx,ppy;
};
queue<pos>q;
int m,n,g[100+1][100+1],v[100+1][100+1]={0};
int xx[]={0,0,0,1,-1};
int yy[]={0,1,-1,0,0};
void bfs()
{
q.push((pos){1,1,0,0,0});
v[1][1]=0;
while(!q.empty())
{
pos tmp=q.front();
q.pop();
int px=tmp.x,py=tmp.y;
for(int i=1;i<=4;i++)
{
int nx=px+xx[i],ny=py+yy[i],ng=tmp.gd;
//***
if(px>=1&&px<=m&&py>=1&&py<=m)
if(g[nx][ny]&&g[px][py])
if(g[nx][ny]!=g[px][py])
ng+=1;
else
pass
else if(g[nx][ny]==0&&g[px][py])
ng+=2;
else if(g[px][py]==0&&g[nx][ny])
if(g[nx][ny]==g[tmp.ppx][tmp.ppy])
pass
else
ng+=1;
else
continue;
else
continue;
//***orz判断
if(ng<v[nx][ny]||v[nx][ny]==-1)
{
q.push((pos){nx,ny,ng,px,py});
v[nx][ny]=ng;
}
}
}
}
int main()
{
read(m),read(n);
for(int i=1;i<=n;i++)
{
int a,b,c;
read(a),read(b),read(c);
g[a][b]=c+1;
}
memset(v,-1,sizeof(v));
bfs();
print(v[m][m]);//CE
return 0;
}
那如何处理魔法？
一个清奇的思路：记录一个点的上一个点（pos结构体中的ppx ppy）。
if(px>=1&&px<=m&&py>=1&&py<=m)
if(g[nx][ny]&&g[px][py])
if(g[nx][ny]!=g[px][py])
ng+=1;
else
pass
else if(g[nx][ny]==0&&g[px][py])
ng+=2;
else if(g[px][py]==0&&g[nx][ny])
if(g[nx][ny]==g[tmp.ppx][tmp.ppy])
pass
else
ng+=1;
else
continue;
else
continue;
line 7：如果下一个点为空，而现在的点有颜色，
line 8：那就花费 2 金币。
为什么呢？
因为这样实际是魔法的情况。
line 9：如果现在的点为空，而下一个点有颜色，
line 10：那若上一个点颜色与下一个点颜色相同，
line 11：无需再花费；
line 12,13：否则仍需花费 1 金币。
为什么呢？
以下面的图为例：
红->空->黄 [图1]
- 把空变红，花 2 金币
- 前进，无需金币
- 前进，走上黄，花 1 金币
红->空->红 [图2]
- 把空变红，花 2 金币
- 前进，无需金币
- 前进，走上红，无需金币
为什么只有这两种情况？因为魔法不能连续使用！
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/98b89eb3d138/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
