前言

一个绿题，风光啊 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<