目录

            题干

                归纳条件

分析：

 1.设变量部分

     2.输入输出部分

         3.核心代码dfs部分 

      完整AC代码

  总结

题干

首先归纳条件

1.格子有三种情况，红，黄，无色

2.上下左右四个方向

3.只能够站在有颜色的地方

4.移动到另一格子时，若同色，则免费，若异色，则1金币，若无色，2金币

5.这道题信息量十分的大

好

我们从头到尾开始

分析

首先是

设变量部分

#include<bits/stdc++.h>
using namespace std;
int a[105][105],b[105][105],m,n,c,t=0,ans=1e9;
int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};

解释一下各个变量 

1.a后来是储存颜色的

2.b不过是储存答案的棋子罢了

3.m,n,c没什么好说的

4.t是记录是否找到，在最后输出的时候有用

5.dx，dy数组是方向，很常规

接下来应该是dfs 部分，但那时核心代码，最后讲

所以

先说

输入输出部分

 cin>>n>>m;
 for(int i=1;i<=n;i++){
 for(int j=1;j<=n;j++){
 b[i][j]=1e9;}}//设个贼大的值，方便求min值
 for(int i=0;i<m;i++){
  int x,y,c;
 cin>>x>>y>>c;
 if(c==0) a[x][y]=2;//红的换成2
 else a[x][y]=1;//黄的还是1
}
 dfs(1,1,0,0);
 if(t==1) cout<<ans<<endl;//找到了    
 else cout<<-1<<endl;//没找到
 }

再解释解释注释没说到的地方

1.直接设x,y,c，不然设数组的话内存又大又麻烦

2. dfs（1，1，0，0） 其中1，1表示初始坐标，第一个0存答案，第二个0表示上次没有使用魔法

最后就是

核心代码dfs部分

void dfs(int x,int y,int cnt,int k){
 if(cnt>=b[x][y]){
  return ;}//小于最小值，回去重新投胎
  b[x][y]=cnt;//投胎成功，更新最小值
  if(x==n && y==n){
  t=1;//到啦，记录一下
  ans=min(ans,cnt);//最小值
  return;
  }
  for(int i=0;i<=3;i++){//四个方向
   int ux=x+dx[i],uy=y+dy[i];
   if(ux<1 || uy<1 || ux>m || uy>m){
   continue;}//边界
   if(a[ux][uy]!=0){//下一个有颜色
   if(a[ux][uy]==a[x][y]) dfs(ux,uy,cnt,0);//同色不花钱，不用魔法
    else dfs(ux,uy,cnt+1,0);//留下买路财1金币
    }
    else {//无色
    if(k==0){//上次没用
    a[ux][uy]=a[x][y];// 魔法的力量
    dfs(ux,uy,cnt+2,1);//两金币，用魔法
    a[ux][uy]=0; 又变回来了}}}}

解释一下一些之前输入输出的设计 

1,为什么红色要换成2储存，看代码应该显而易见了（因为0储存无色）；

2.dfs（1，1，0，0）应该可以理解了

ux uy真是好东西

储存方向，实在是太舒服啦！！

现在奉上完整AC代码 

完整AC代码

#include<bits/stdc++.h>
using namespace std;
int a[105][105],b[105][105],m,n,c,t=0,ans=1e9;
int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
void dfs(int x,int y,int cnt,int k){
 if(cnt>=b[x][y]){
  return ;}
  b[x][y]=cnt;
  if(x==n && y==n){
  t=1;
  ans=min(ans,cnt);
  return;
  }
  for(int i=0;i<=3;i++){
   int ux=x+dx[i],uy=y+dy[i];
   if(ux<1 || uy<1 || ux>m || uy>m){
   continue;}
   if(a[ux][uy]!=0){
   if(a[ux][uy]==a[x][y]) dfs(ux,uy,cnt,0);
    else dfs(ux,uy,cnt+1,0);
    }
    else {
    if(k==0){
    a[ux][uy]=a[x][y];
    dfs(ux,uy,cnt+2,1);
    a[ux][uy]=0;}}}}
 int main(){
 cin>>n>>m;
 for(int i=1;i<=n;i++){
 for(int j=1;j<=n;j++){
 b[i][j]=1e9;}}
 for(int i=0;i<m;i++){
  int x,y,c;
 cin>>x>>y>>c;
 if(c==0) a[x][y]=2;
 else a[x][y]=1;
}
 dfs(1,1,0,0);
 if(t==1) cout<<ans<<endl;
 else cout<<-1<<endl;
 }

总结

dfs yyds

谢谢，欢迎讨论！