我感觉跟题解没什么区别啊？
by GoldenFishX @ 2019-12-17 19:39:20
@[未知用户](/user/156353) 剪枝呢？QWQ
by qian_shang @ 2019-12-17 19:47:01
@[qian_shang](/user/64175)
```
if(jb>minjb[x][y]||jb>=ans)//如果这时的金币已经大于最小值的答案了，那么返回。
return 0;
```
by GoldenFishX @ 2019-12-17 19:48:27
@[未知用户](/user/156353) 好吧，第一次看到把剪枝放这里的
by qian_shang @ 2019-12-17 19:54:34
@[qian_shang](/user/64175)
这不是重点......
by GoldenFishX @ 2019-12-17 19:56:57
@[未知用户](/user/156353) 剪枝没到位啊
by S1gMa @ 2020-03-03 14:18:31
```
#include<bits/stdc++.h>
using namespace std;
int xx[4]={1,0,0,-1},yy[4]={0,1,-1,0},a[105][105],vis[105][105],ans=2e9,m,n,minjb[105][105];
//a[i][j]表示第i行第j列放的颜色，1 代表黄色， 0代表红色 ，-1表示无色
//？vis[i][j]=0表示没有访问过，=1表示访问过
//第x行第y列 ,mf是否可以有魔法，1表示可以有魔法 ，0表示没有魔法
int dfs(int x,int y,int jb,int mf)//jb是已经用了多少金币
{
int nx,ny;
if(jb<minjb[x][y])
minjb[x][y]=jb;
else return 0;
if(x==m&&y==m)//到达终点
{
if(jb<ans)//如果金币小于最小值，那么把最小值变成用的金币的个数
ans=jb;
return 0;
}
for(int i=0;i<4;i++)
{
if(jb>minjb[x][y]||jb>=ans)//如果这时的金币已经大于最小值的答案了，那么返回。
return 0;
nx = x + xx[i];
ny = y + yy[i];
if(nx==0||ny==0||nx>m||ny>m||vis[nx][ny]==1||(a[nx][ny]==-1&&mf==0))
{
continue;
}
if(a[nx][ny]==-1&&mf==1)//使用魔法
{
vis[nx][ny]=1;
a[nx][ny]=a[x][y];
dfs(nx,ny,jb+2,0);
a[nx][ny]=-1;
vis[nx][ny]=0;
}
else if(a[x][y]==a[nx][ny])//格子颜色一样
{
vis[nx][ny]=1;
dfs(nx,ny,jb,1);
vis[nx][ny]=0;
}
else if(a[x][y]!=a[nx][ny])//格子颜色不一样
{
vis[nx][ny]=1;
dfs(nx,ny,jb+1,1);
vis[nx][ny]=0;
}
}
}
int main()
{
vis[1][1]=1;
int i,j,x,y,z;
cin>>m>>n;
for(i=0;i<=m;i++)
{
for(j=0;j<=m;j++)
{
a[i][j]=-1;
minjb[i][j]=2e9;
}
}
for(i=0;i<n;i++)
{
cin>>x>>y>>z;
a[x][y]=z;
}
dfs(1,1,0,1);
if(ans!=2e9)
cout<<ans;
else
cout<<-1;
return 0;
}
```
by S1gMa @ 2020-03-03 14:18:49
AC代码
by S1gMa @ 2020-03-03 14:19:27
@[Var1ous](/user/111016) %%%%Orz
by GoldenFishX @ 2020-03-03 14:52:46