代码如下
#include <iostream>
using namespace std;
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
char ch[505][505];
bool b[505][505],flag=false;
int minn=0x7fffffff,n,m,fx,fy,tx,ty;
struct link{
int x,y,sum;
}p[1001000];
void bfs(int x,int y)
{
int h=1,l=1;
b[x][y]=1;
p[1].x=x;
p[1].y=y;
p[1].sum=int(ch[1][1]-64);
while(h<=l)
{
for(int i=0; i<=3; i++)
{
tx=p[h].x+dx[i];
ty=p[h].y+dy[i];
if(b[tx][ty]==0 && tx<=n && ty<=m && ty>=1 && tx>=1)
{
l++;
p[l]={(link){tx,ty,p[h].sum+int(ch[tx][ty]-64)}};
b[tx][ty]=1;
if(tx==fx && ty==fy)
{
minn=min(minn,p[l].sum);
flag=true;
}
}
}
h++;
}
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cin>>ch[i][j];
if(ch[i][j]=='M' || ch[i][j]=='Y' || ch[i][j]=='T' || ch[i][j]=='H') b[i][j]=1;
else b[i][j]=0;
}
}
fx=n;
fy=m;
if(b[1][1]==true || b[n][m]==true)
{
cout<<"-1";
return 0;
}
bfs(1,1);
if(flag==true) cout<<minn;
else cout<<"-1";
}