传送
这看起来有点像个搜索，那我们就用搜索试试。
dfs?bfs?
其实都可以，但是窝只会dfs.。
既然这里要用dfs,那么就要把每次搜到(m,m)时，使用的金币数量进行比较，取最小值。
在搜索过程中肯定会遇到很多不是最优解的情况。既然不是最优解，那么我们可以用某些方式在搜索过程中就把这些情况给剪掉。（也就是剪枝）我们不妨再开一个二维数组best，best[i][j]表示走到点(i,j)所用的最少金币数量。这样搜索到点(i,j)时，如果当前花费的金币总数不小于best[i][j],那么就算这种情况能够到达终点，它也一定不是最优解，所以我们直接返回，不再搜索。这样就可以节省很多的时间（至少不会TLE）
再考虑一些细节
这里我们就不判断每个点是否到过了，因为在上面的剪枝中，第二次到达一个搜索过的点，花费的金币肯定不比第一次到达时花费的少。
在搜索时，我们只搜索有颜色的点。对于那些可以使用魔法的无色格子，我们就直接把它设成有颜色的，并且标记已经使用过魔法。在回溯的时候再使它的颜色变为无色就好。
这里红色是0，黄色是1，而那些没有颜色的点的初始值也是0。所以我们在输入颜色的时候，将有颜色的点的颜色+1，就可以区分了。
代码：
#include<bits/stdc++.h> using namespace std; int m,n,ma[109][109],be[109][109];//be就是best,ma就是map(地图) int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; int read()//快读 {char ch=getchar();int x=0;bool f=0;while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}f?x=-x:x=x;return x; } void dfs(int nowx,int nowy,int cost,bool magic) {if(nowx==m&&nowy==m){be[m][m]=min(be[m][m],cost);return ;}if(cost>=be[nowx][nowy])return ;be[nowx][nowy]=cost;for(int i=0;i<=3;i++){int ex=nowx+dx[i],ey=nowy+dy[i];if(ex>=1&&ex<=m&&ey>=1&&ey<=m){if(ma[ex][ey]!=0)//只搜索有颜色的点（无色可以覆盖成有色） {if(ma[ex][ey]==ma[nowx][nowy])dfs(ex,ey,cost,0);else dfs(ex,ey,cost+1,0); }else if(magic==0)//对于无色的点，看是否能使用魔法 {ma[ex][ey]=ma[nowx][nowy];dfs(ex,ey,cost+2,1);ma[ex][ey]=0;//一定要记得回溯啊 }}} } int main() {m=read();n=read();for(int i=1;i<=n;i++){int x=read(),y=read(),c=read();c++;ma[x][y]=c;}memset(be,63,sizeof(be));dfs(1,1,0,0);if(be[m][m]<1061109567)//memset之后be的值是1061109567printf("%d\n",be[m][m]);//be[m][m]就是最后的解else printf("-1");return 0; }