```
#include <iostream>
#include <algorithm>
const int Inf = 1e9;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };
const int N = 110;
int f[N][N];
int m, n;
int dist[N][N];
void dfs(int x, int y, int coin, bool canUseMagic, int nowColor, bool prevMagic); //意义不用我说了吧。。。
int main()
{
std::fill(f[0], f[0] + N * N, -1);
std::fill(dist[0], dist[0] + N * N, Inf);
int x, y, c;
std::cin >> m >> n;
for (int i = 0; i < n; ++i)
{
std::cin >> x >> y >> c;
f[x - 1][y - 1] = c;
}
dfs(0, 0, 0, true, f[0][0], true);
if (dist[m - 1][m - 1] == Inf)
dist[m - 1][m - 1] = -1;
std::cout << dist[m - 1][m - 1] << std::endl;
}
void dfs(int x, int y, int coin, bool canUseMagic, int nowColor, bool prevMagic)
{
if (coin >= dist[x][y])
return;
dist[x][y] = coin;
if (x == m - 1 && y == m - 1)
return;
if (!prevMagic)
canUseMagic = true;
for (int i = 0; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < m)
{
if (nowColor == f[nx][ny])
dfs(nx, ny, coin, canUseMagic, nowColor, canUseMagic);
else if (f[nx][ny] == -1 && canUseMagic)
dfs(nx, ny, coin + 2, false, nowColor, true);
else if (f[nx][ny] != -1)
dfs(nx, ny, coin + 1, canUseMagic, f[nx][ny], canUseMagic);
}
}
}
```
对比一下这篇题解，剪枝部分没有区别
by halehu @ 2022-06-09 22:00:37
顺便说明一下，0，1即题意，-1代表无色，2代表魔法赋予的“0”颜色，3代表魔法赋予的“1”颜色
by halehu @ 2022-06-09 22:08:49
```if(sum>a[x][y])return;```改成```if(sum>=a[x][y])return;```
by Carey_chen @ 2022-06-15 20:07:13
太感谢大佬了
没想到相等的情况竟然有那么多种
@[Carey_chen](/user/516836)
by halehu @ 2022-07-06 14:25:10
@[Carey_chen](/user/516836) 同谢dalao。震惊了
by f070331 @ 2022-08-23 21:47:37