题目

参考题目:[https://www.luogu.org/problemnew/show/P3956]

相信大家都做过这道题吧，毕竟真的是到很明显的搜索/dp dp就不说了，有兴趣可以去题解去瞅瞅，不过因为有可能往回走，dp写起来会很麻烦让你怀疑你写的不是dp 但是同样是因为有可能回走，dfs与bfs无法进行像 bool x[][] 这样的剪枝办法（已经走过的路不走的办法） 所以就需要优化

骗分

既然是考试题目，那么我就就可以骗分

5 分

---

输出特殊状况—’-1′

10 分

---

在5分的情况下考虑输出0的情况

15-65 分

---

dfs大法，不加任何优化版 但是分数可能会有一定波动，需要注意下面几点

• 尽可能递归 RE
• 做一点微小的剪枝
• 平时代码习惯不好可能会比较容易得低
• 小心魔法

注意完以上几点，你就是一等大佬了

65 分

---

在15-65分做法中去除向上和向左，防止打转

100 分做法

博主在这里说两种搜索法-bfs/dfs 最短路以及dp大家有心情可以试试 这题用最短路这是杀鸡用牛刀 使用这两种方法都要建一个best[][]数组表当前最优花费，这样就可以避免一些不必要的地方，达成剪枝的目的。 先单独拿出来一行代码讲一下

col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col

可以转化为这个

int wh(){
    if(col[now.x][now.y]!=0) return col[now.x][now.y];
    else return temp.tu.col;
}
wh();

这个符号我们叫三目运算符/问号表达式

bfs

---

#include <cstdio>
#include <cstring>
using namespace std;
struct que{
    int tu_col,money,x,y;
// tu_col 目前变化的颜色
// money 目前所花钱数
// x y 目前走到(x,y)上
}q[110000];// q[] 队列
int n,m,x,y,c;
// dx[] dy[] 增量
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
// best[i][j] 目前位于(i,j)的已知最优解
// col[i][j] (i,j)格子上的颜色
int main(){
    memset(best,0x3f,sizeof(best));// 初始化
// 读入
   scanf("%d%d",&m,&n);
   for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
// 加入队列首
    q[1].x=q[1].y=1;
    q[1].money=q[1].tu_col=0;
    int h,t;
    h=t=1;
    best[1][1]=0;// 第一个格子设为0
    while(h<=t){// 开始bfs
        que now;
        now=q[h];
// now 仅仅为了方便写，在下面的循环中可替换为q[h]，也就是用于储存队列首
        for(int i=0;i<4;i++){// 模拟上下左右
            que temp=q[h];
            temp.x+=dx[i];
            temp.y+=dy[i];
            // temp 用于临时修改
            if(temp.x<=0||temp.y<=0||temp.x>m||temp.y>m) continue;// 判断越界
            if(col[temp.x][temp.y]==0/*如果当前格子上没有颜色*/&&temp.tu_col==0/*并且上一个格子没有用魔法*/){
                if(temp.money+2<best[temp.x][temp.y]){// 如果当前解优于已知最优解，才能放入队列
                    temp.money+=2;
                    temp.tu_col=col[now.x][now.y];// 存入临时颜色
                    q[++t]=temp;// 加入队列
                    best[temp.x][temp.y]=temp.money;// 更新 best 数组
                }
            }
            else if(col[temp.x][temp.y]!=0&&col[temp.x][temp.y]!=(col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col)){// 颜色不相等
                 if(temp.money+1<best[temp.x][temp.y]){// 不解释
                    temp.money+=1;
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
            else if(col[temp.x][temp.y]!=0){// 接下来只有可能颜色相等
                if(temp.money<best[temp.x][temp.y]){
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
        }
        h++;// 踢出对首
    }
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);// 不是预设值就输出
    else printf("-1");// 是预设值说明没有路通向那，输出-1
}

dfs

---

请参照 bfs 方法的注释来理解这个，所有变量含义一样

#include <cstdio>
#include <cstring>
using namespace std;
int n,m,x,y,c;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
void dfs(int x,int y,int tu_col,int money){
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<=0||ty<=0||tx>m||ty>m) continue;
        if(col[tx][ty]==0&&tu_col==0){
            if(money+2<best[tx][ty]){
                best[tx][ty]=money+2;
                dfs(tx,ty,col[x][y],money+2);
            }
        }
        else if(col[tx][ty]!=0&&col[tx][ty]!=(col[x][y]!=0?col[x][y]:tu_col)){
            if(money+1<best[tx][ty]){
                best[tx][ty]=money+1;
                dfs(tx,ty,0,money+1);
            }
        }
        else if(col[tx][ty]!=0){
            if(money<best[tx][ty]){
                best[tx][ty]=money;
                dfs(tx,ty,0,money);
            }
        }
    }
}
int main(){
    memset(best,0x3f,sizeof(best));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
    best[1][1]=0;
    dfs(1,1,0,0);
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);
    else printf("-1");
}

END

要是考场上没有删掉自己的dp就好了qwq ]]>