@[Adis_FireDevil](/user/115067) 我建议你再开一个数组，用来存到达每个点的最少步数。
by GoldenFishX @ 2019-11-13 20:38:06
@[Adis_FireDevil](/user/115067) 看我用<======指的部分
by GoldenFishX @ 2019-11-13 20:43:31
```
#include<bits/stdc++.h>
using namespace std;
int df5[111][111],n,k,mingold[111][111]; //<==== //df5记录每一个点的颜色
bool bd[111][111]; //bd[i][j]数组记录df5[i][j]是否走过
int way[5][3]= {{0,0,0},{0,0,1},{0,0,-1},{0,1,0},{0,-1,0}}; //way数组为可以移动的方向
int ans=1000000000;
int dfs(int x,int y,int nomagic,int gold,int color) { //x,y为横纵坐标，nomagic为是否能用魔法，gold指需要的金币，color指当前的颜色
//对于nomagic变量，若为1则不能用魔法，0则能用魔法
if(x<=0||x>n||y<=0||y>n)return 0; //判断是否超出边界
if(gold>mingold[x][y])//<===//判断是否已不是最优解
return 0;
else
mingold[x][y]=gold;//<====
if(bd[x][y])return 0; //判断该点是否走过
if(x==n&&y==n) {
ans=gold; //记录答案，一定是最优解
return 0;
}
bd[x][y]=true; //记录该点已走过
for(int i=1; i<=4; i++) {
int xx=x+way[i][1],yy=y+way[i][2];
if(!nomagic&&df5[xx][yy]==0)dfs(xx,yy,1,gold+2,color);
else if(df5[xx][yy]==color)dfs(xx,yy,0,gold,color);
else if(df5[xx][yy]!=color&&df5[xx][yy]!=0)dfs(xx,yy,0,gold+1,df5[xx][yy]);
}
bd[x][y]=false; //回溯
}
int main(){
int s1,s2,s3;
cin>>n>>k;
for(int i=1; i<=k; i++) {
cin>>s1>>s2>>s3;
df5[s1][s2]=s3+1;
}
for(int i=0;i<111;i++)
for(int j=0;j<111;j++)
mingold=2e9;//<===给个大数
dfs(1,1,0,0,df5[1][1]);
if(ans==1000000000)cout<<-1;
else cout<<ans;
}
```
by GoldenFishX @ 2019-11-13 20:47:04
谢谢大佬
by Adis_FireDevil @ 2019-11-14 16:16:31