搜索(m^4)

• 从起点开始搜索每个格子，然后记录当前答案，更新最小值。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int color[N][N],dist[N][N];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int n,m;
void dfs(int x,int y,int gold,int magic)
{
    if(dist[x][y]<=gold) return ;//最优性剪枝
    dist[x][y]=gold;
    if(x==n&&y==n) return;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<1||a>n||b<1||b>n) continue;
        if(color[a][b]==-1) //走到的地方是空白的
        {
            if(magic) continue;//连续两个无色的
            else
            {
                color[a][b]=color[x][y]; //使用魔法，将当前格子变颜色(其实是需要枚举的)
                dfs(a,b,gold+2,true);
                color[a][b]=-1;
                
                //color[x][y]==color[a][b]=color[p][q]  花费是2
                
                //color[x][y]==color[a][b]->color[a][b]!=color[p][q]  3
                //color[x][y]!=color[a][b]->color[a][b]==color[p][q]  3
             }
        }
        else if(color[a][b]==color[x][y]) dfs(a,b,gold,false); //同一种颜色
        else dfs(a,b,gold+1,false); //不同颜色
    }
}
int main()
{
    cin>>n>>m;
    memset(color,-1,sizeof color); //初始无色
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        color[x][y]=z; //颜色
    }
    memset(dist,0x3f,sizeof dist);
    dfs(1,1,0,false);
    if(dist[n][n]==0x3f3f3f3f) cout<<-1;
    else cout<<dist[n][n];
    return 0;
}

最短路(spfa $m^2$)

• 使用spfa建图，进行单源最短路。

#include<bits/stdc++.h>
using namespace std;
const int N=110,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
struct Node{ //位置和当前颜色
    int x,y,z;
};
int dist[N][N][2];
bool st[N][N][2];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int spfa()
{
    queue<Node> q;
    memset(dist,0x3f,sizeof dist);
    dist[1][1][g[1][1]]=0; //起点
    q.push({1,1,g[1][1]}); //入队
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        st[t.x][t.y][t.z]=false; //不在队列之中
        for(int i=0;i<4;i++)
        {
            int x=t.x+dx[i],y=t.y+dy[i],d,z; //d表示花费,z 表示当前点的颜色
            if(x<0||x>n||y<0||y>n) continue; //越界
            int c1=g[t.x][t.y],c2=g[x][y];
            if(c2!=-1) //c2有颜色
            {

                if(t.z==c2) d=0; //颜色相同
                else d=1;
                z=c2; //往下传递
                if(dist[x][y][z]>dist[t.x][t.y][t.z]+d) //可以更新最短路
                {
                    dist[x][y][z]=dist[t.x][t.y][t.z]+d;
                    if(!st[x][y][z])
                    {
                        q.push({x,y,z});
                        st[x][y][z]=true;
                    }
                }
            }
            else if(c1!=-1) //c1有颜色(c2没有颜色)
            {
                d=2; //最小花费
                for(z=0;z<2;z++)
                {
                    if(z!=c1) d++; //多的花费
                    if(dist[x][y][z]>dist[t.x][t.y][t.z]+d) //更新最短路
                    {
                        dist[x][y][z]=dist[t.x][t.y][t.z]+d;
                        if(!st[x][y][z])
                        {
                            q.push({x,y,z});
                            st[x][y][z]=true;
                        }
                    }
                    if(z!=c1) d--; //还原花费
                }
            }
        }
    }
    int res=min(dist[n][n][0],dist[n][n][1]); //距离最小值
    if(res==INF) res=-1;
    return res;
}
int main()
{
    cin>>n>>m;
    memset(g,-1,sizeof g);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=c;
    }
    cout<<spfa()<<endl;
    return 0;
}