最新要闻

广告

手机

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

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

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

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

家电

「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<

关键词: