最新要闻

广告

手机

TATA木门第八届静音日 带你解读“有降噪 不怕闹”

TATA木门第八届静音日 带你解读“有降噪 不怕闹”

 兴证全球基金：出资5000万元自购旗下权益类公募基金

兴证全球基金：出资5000万元自购旗下权益类公募基金

家电

  1. 首页
  2. 移动通信
  3. 内容

「NOIP2017 普及组」棋盘 题解

来源：博客园

前言

一个绿题，风光啊 QwQ


【资料图】

题面

传送门

思路

怎么走

我们定义一个函数 dfs(x,y,coin,can,color)

x,y表示坐标，coin表示当前的金币数量，color表示当前坐标的颜色，can表示当前是否能施展魔法。

再加一个mp数组记录颜色，-1表示无颜色，0表示红色，1表示黄色

为什么不直接使用 mp[x][y]获取颜色呢？从题目中可知，如果下一个格子没有颜色，需要施展“魔法”改变颜色才可以移动，而且这个魔法是临时的，离开之后就会复原，所以需要传一个颜色进去，不然会影响下一步的颜色判定。

与大部分棋盘类dfs相似，我们定义两个数组fx,fy来记录每个方向两轴的变化：const int fx[5]={0,-1,1,0,0},fy[5]={0,0,-1,1}，写一个1-4的循环，每一次的nx,ny(下一个方向的坐标)就为x+fx[i],y+fy[i]。

搜索就很简单了，如果mp[nx][ny]==color，那么直接搜索：

dfs(nx,ny,coin,1,color);

不然的话，如果mp[nx][ny]!=-1（即不是无颜色），搜索，并将金币+1：

dfs(nx,ny,coin+1,1,mp[nx][ny]);

否则就没有颜色了，施展魔法将其变为当前格子颜色，因为魔法只能施展一次，前面的can变量就起效了，如果上一次施展过魔法，can为0，就不可以走这个格子了，然后金币+2，即mp[nx][ny]==-1&&can&&coin+2。

dfs(nx,ny,coin+2,0,color);

接下来我们需要一些边界条件，如果到达目标点，即为x==m&&y==m时，退出循环并记录最小值。如果x和y超过合法范围也要返回：

if(x>m||y>m||x<1||y<1) return;if(x==m&&y==m){    minc=min(minc,coin);    return;}

除此之外，你需要一个vis数组记录当前走过的部分（回溯！！！），不然你会得到壮观的MLE：

这就是简单的搜索逻辑。

剪枝

作为一个普及组的T3，哪有那么容易让你拿分呢？

终于，你写出了代码，你披星戴月、奋不顾身，只为证明——只因它太暴力：

#include using namespace std;const int inf=0x7fffffff,fx[5]={0,1,-1,0,0},fy[5]={0,0,0,1,-1};int m,n,mp[1145][1145],minc=inf,nx,ny,vis[1145][1145];void dfs(int x,int y,int coin,bool can,int color){if(coin>minc) return;if(vis[x][y]) return;    if(x>m||y>m||x<1||y<1) return;if(x==m&&y==m){        // cout<<"c:"<>m>>n;for(int i=1;i<=n;i++){int x,y,c;cin>>x>>y>>c;mp[x][y]=c;}dfs(1,1,0,1,mp[1][1]); if(minc==inf) cout<<-1;else cout<

显然，这需要剪枝。

对于剪枝来说，有这几种思路：

  1. 发现当前金币已经比最小的多了，就不用搜下去了
  2. 在循环中就可以判断搜索合法性了，减小函数调用开销（PS：我习惯把这玩意写在边界条件上面，看起来差不多，实则增加了函数调用开销，调用后才返回，花费显然很大
  3. 记忆化，记录走到当前坐标合法路径的最小金币，如果超过就可以不搜了，比第一个更高级

关于记忆化，我们可以定义一个数组minmp[1145][1145]并初始化为inf（用memset需要改为127）

然后在循环里面判断即可。

代码

终于可以上代码了：

#include using namespace std;const int inf=0x7fffffff,fx[5]={0,1,-1,0,0},fy[5]={0,0,0,1,-1}; //每个方向xy变化int m,n,mp[1145][1145],minc=inf,nx,ny,vis[1145][1145],minmp[1145][1145]; //mp记录颜色，minc为最小金币，vis用于回溯。minmp为某个当前最小值void dfs(int x,int y,int coin,bool can,int color){ //定义见上if(x==m&&y==m){ //边界        // cout<<"c:"<m||ny>n||nx<1||ny<1||vis[nx][ny]) continue; //不成立条件写循环里，减小开销if(color==mp[nx][ny]&&coin>m>>n;for(int i=1;i<=n;i++){ //输入数据int x,y,c;cin>>x>>y>>c;mp[x][y]=c;}dfs(1,1,0,1,mp[1][1]); if(minc==inf) cout<<-1; //没搜到else cout<

关键词：