中文题我就不解释题意了。

思路：很明显这个棋盘很小，只有10000个格子，那么n平方的算法就能过了，那就直接dfs暴力，可以加一个小优化，如果当前使用的钱币已经大于之前所算的最小钱币数，就不继续往下算了。

程序

using namespace std;const int dx[]={-1,0,1,0},dy[]={
   0,-1,0,1};const int maxn=110,maxm=1e9+7;int dp[maxn][maxn],mp[maxn][maxn];int m,n,ans=maxm;void dfs(int x,int y,int sum,bool flag){    if(x<1 || y<1 || x>m || y>m)    return;    if(!mp[x][y])    return;    if(sum>=dp[x][y])    return;    dp[x][y]=sum;    if(x==m && y==m)    {        if(sum
    
     >m>>n;    for(int i=1;i<=n;i++)    {        int x,y,c;        cin>>x>>y>>c;        mp[x][y]=c+1;    }    dfs(1,1,0,0);    if(ans==maxm)    cout<<-1;    else    cout<