题目传送门：
题目描述：
有一个 \(m * m\) 的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1 个金币。
另外， 你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？
输入格式：
第一行包含两个正整数 m, n，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。
接下来的n行，每行三个正整数 x, y, c ， 分别表示坐标为(x,y) 的格子有颜色 c 。
其中c=1 代表黄色，c=0 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为(1,1) ，右下角的坐标为(m,m) 。
棋盘上其余的格子都是无色。保证棋盘的左上角，也就是(1,1) 一定是有颜色的。
输出格式：
一个整数，表示花费的金币的最小值，如果无法到达，输出 -1 。
[算法分析：]
可以用bfs,dfs,SPFA,DP来做，最简单的还是dfs.
如何处理魔法：
在dfs函数内新增一个bool型的参数fl
fl=1表示上一步使用过魔法，则这一步不能再次使用；
把使用过魔法的格子变成上一个格子的颜色：
假设上一个格子的颜色为1，则这个格子的颜色也变成1当向其他三个方向有路可走的时候，若是去向的格子颜色为1，则变成1是最优解，若是去向的格子颜色为0，则这个格子变成1的花费与变成0的等效。
综上所述，使用魔法将当前格子变成上一个格子的颜色最优。
使用XOR运算来求出从一个有颜色的格子到另一个有颜色的格子的费用，注意位运算的优先级低，与四则运算同时使用时要加括号。
但是这样dfs是会超时的，考虑一些剪枝：
当当前的花费值大于当前的最小花费值时，返回
更快的剪枝：
走到当前格子的花费大于走到这个格子的最小花费时，返回
使用一个二维数组f，f[i][j]表示走到格子\((i,\ j)\)时的最小花费，则dfs就变成了记忆化搜索。
\([Code:]\)
#include#include #include #define INF 2e9using namespace std;const int MAXN = 100 + 1;const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};int n, m, ans = INF;int a[MAXN][MAXN], f[MAXN][MAXN];bool vis[MAXN][MAXN];void dfs(int x, int y, int sum, bool fl) { if(x == n && y == n) { ans = min(ans, sum); return; } if(sum >= f[x][y]) return; f[x][y] = sum; for(int i=0; i<4; ++i) { int xx = x + dx[i], yy = y + dy[i]; if(!vis[xx][yy] && xx>0 && yy>0 && xx<=n && yy<=n) { vis[xx][yy] = 1; if(a[xx][yy] != -1) dfs(xx, yy, sum + (a[x][y]^a[xx][yy]), 0); else if(!fl){ a[xx][yy] = a[x][y]; dfs(xx, yy, sum + 2, 1); a[xx][yy] = -1; } vis[xx][yy] = 0; } }}int main() { memset(f, 0x7f, sizeof(f)); memset(a, -1, sizeof(a)); scanf("%d%d", &n, &m); for(int i=1; i<=m; ++i) { int x, y, c; scanf("%d%d%d", &x, &y, &c); a[x][y] = c; } dfs(1, 1, 0, 0); if(ans == INF) printf("-1"); else printf("%d", ans);}