题目链接：P3956
一开始看到坐上到右下以为是DP，后来看到要求的是最优路线，不是有多少路线，数据范围是100，如果所有路线都来一遍的话是2的一百次方，显然不行，那么就需要剪枝，本题一共有两个点可以剪，一个是下一步出地图了，return,还有就是如果走到当前格子，所用的金币数大于之前走这里时所用的最少的金币，则剪掉，也就是说要把从左上角走到每个点的最小值都记录下来。
本题还有个条件是魔法，用一个参数记录一下当前是否使用过魔法即可，使用魔法的时候进行回溯。
AC代码：

#include<bits/stdc++.h>
using namespace std;
int m;
int dir[4][2] = { 1,0,0,1,-1,0,0,-1 };
int numbers[105][105];
int ans[105][105];
int res = 100000000;
void  dfs(int r, int c, int k,int p)
{int a, b;if (k >=ans[r][c])return;ans[r][c] = k;//cout << r << " " <<  << endl;if (r == m && c == m){res= min(res, k);return;}for (int i = 0; i < 4; i++){a = r + dir[i][0];b = c + dir[i][1];if (a >= 1 && a <= m && b >= 1 && b <= m){if (numbers[a][b] && numbers[r][c] == numbers[a][b])dfs(a, b, k,1);else if (numbers[a][b] && numbers[r][c] != numbers[a][b])dfs(a, b, k + 1,1);else if (!numbers[a][b]){if (p == 0)continue;numbers[a][b] = numbers[r][c];dfs(a, b, k + 2,0);numbers[a][b] = 0;}}}
}
int main()
{int  n; cin >> m >> n;for (int i = 0; i < n; i++){int a, b, c; cin >> a >> b >> c;numbers[a][b] = c + 1;}memset(ans, 0x7f, sizeof(ans));dfs(1, 1, 0, 1);if (res == 100000000)cout << -1;else cout << res;
}