强行建图跑最短路

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 100;
const int INF = 2147483647;
int m, n; // 棋盘大小 m*m，n 枚棋子
int col[MAXM + 5][MAXM + 5];
// 真的创建虚拟点 1~tot
int tot, idx[MAXM + 5][MAXM + 5][3];
vector<pair<int, int>> e[MAXM * MAXM * 2 + 5];
void addEdge(int x, int y, int a, int b)
{
    // 两个同色的到不了
    if (col[x][y] == 0 && col[a][b] == 0)
        return;
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
        {
            if (col[x][y] && col[x][y] != i)
                continue;
            if (col[a][b] && col[a][b] != j)
                continue;
            int u = idx[x][y][i];
            int v = idx[a][b][j];
            int w = 0;
            if (i != j)
                w++; // 异色花一块钱
            if (col[a][b] == 0)
                w += 2; // 变色多花两块钱
            e[u].push_back({v, w});
        }
}
bool vis[MAXM * MAXM * 2 + 5];
int dis[MAXM * MAXM * 2 + 5];
priority_queue<pair<int, int>> pq;
void dijkstra(int s)
{
    for (int i = 0; i <= tot; i++)
    {
        vis[i] = false;
        dis[i] = INF;
    }
    dis[s] = 0;
    pq.push({-0, s});
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                pq.push({-dis[v], v});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        col[x][y] = z + 1;
    }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
        {
            idx[i][j][1] = ++tot;
            idx[i][j][2] = ++tot;
        }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
        {
            if (i > 1)
                addEdge(i, j, i - 1, j);
            if (i < m)
                addEdge(i, j, i + 1, j);
            if (j > 1)
                addEdge(i, j, i, j - 1);
            if (j < m)
                addEdge(i, j, i, j + 1);
        }
    dijkstra(idx[1][1][col[1][1]]);
    int ans = min(dis[idx[m][m][1]], dis[idx[m][m][2]]);
    if (ans == INF)
        cout << -1;
    else
        cout << ans;
    return 0;
}

DFS

#include<iostream>
#include<cstring>
using namespace std;
char Map[105][105];
int ans[105][105];
int n,m;
bool flag;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y,int z, char col,int magic)
{
    if(Map[x][y]=='2'){
        if(magic==1) return;
        magic=1;
        z+=2;
        col=col;
    }else if(Map[x][y]==col){
        magic=0;
        z+=0;
        col=col;
    }else{
        magic=0;
        z+=1;
        col=Map[x][y];
    }
    if(z>=ans[x][y]) return ;
    ans[x][y]=z;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx>=1&&tx<=n&&ty>=1&&ty<=n)  
        {
            dfs(tx,ty,z,col,magic);
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(Map,'2',sizeof(Map));
    memset(ans,0x3f,sizeof(ans));
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        Map[x][y]='0'+z;
    } 
    dfs(1,1,0,Map[1][1],0);
    if(ans[n][n]==0x3f3f3f3f){
        cout<<-1<<endl;
    }else{
        cout<<ans[n][n]<<endl;
    }
    return 0;
}

BFS

#include <bits/stdc++.h>
using namespace std;
char Map[105][105];
int ans[105][105];
int n, m;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct Point
{
    int x, y; //位置
    //走到当前位置之前的状态：金币，颜色，魔法
    int money, color, magic;
};
queue<Point> q;
void bfs(int sx, int sy)
{
    q.push((Point){sx, sy, 0, Map[sx][sy], 0});
    while (!q.empty())
    {
        Point now = q.front();
        q.pop();
        if (Map[now.x][now.y] == '2')
        {
            if (now.magic == 1)
                continue;
            now.money += 2;
            now.color = now.color;
            now.magic = 1;
        }
        else if (Map[now.x][now.y] == now.color)
        {
            now.money += 0;
            now.color = Map[now.x][now.y];
            now.magic = 0;
        }
        else
        {
            now.money += 1;
            now.color = Map[now.x][now.y];
            now.magic = 0;
        }
        if (now.money >= ans[now.x][now.y])
            continue;
        ans[now.x][now.y] = now.money;
        for (int i = 0; i < 4; i++)
        {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            if (1 <= nx && nx <= n &&
                1 <= ny && ny <= n)
                q.push((Point){nx, ny, now.money, now.color, now.magic});
        }
    }
}
int main()
{
    cin >> n >> m;
    memset(Map, '2', sizeof(Map));
    memset(ans, 0x3f, sizeof(ans));
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        Map[x][y] = '0' + z;
    }
    bfs(1, 1);
    if (ans[n][n] == 0x3f3f3f3f)
        cout << -1 << endl;
    else
        cout << ans[n][n] << endl;
    return 0;
}