动态规划不行吗
错误百分之95，用的三维dp，dp[x][y][c]表示到达位置(x,y)颜色为c时的最小花费，无色格子贪心变为前一个格子的颜色，1e9代表走不到
#include<bits/stdc++.h>
using namespace std;
int a[101][101];
int dp[101][101][3];
int get(int x,int y,int nx,int ny){
int res = 1e9;
if(a[x][y]){
res = min(dp[nx][ny][a[x][y]],dp[nx][ny][3-a[x][y]]+1);
}
else{
if(a[nx][ny])dp[x][y][a[nx][ny]] = min(dp[x][y][a[nx][ny]],dp[nx][ny][a[nx][ny]]+2);
}
return res;
}
int main(){
int i,j,m,n,x,y,c;
scanf("%d%d",&m,&n);
for(i=0;i<n;++i){
scanf("%d%d%d",&x,&y,&c);
if(c==0)a[x][y] = 2;
else a[x][y] = 1;
}
for(i=1;i<=m;++i){
for(j=1;j<=m;++j){
for(int k=0;k<3;++k)dp[i][j][k] = 1e9;
}
}
dp[1][1][a[1][1]] = 0;
for(i=2;i<=m;++i){
dp[i][1][a[i][1]] = get(i,1,i-1,1);
dp[1][i][a[1][i]] = get(1,i,1,i-1);
}
for(i=2;i<=m;++i){
for(j=2;j<=m;++j){
dp[i][j][a[i][j]] = min(get(i,j,i,j-1),get(i,j,i-1,j));
}
}
int ans = 1e9;
for(i=0;i<3;++i)ans = min(ans,dp[m][m][i]);
if(ans==1e9)printf("-1\n");
else printf("%d\n",ans);
return 0;
} 