本题使用记忆化搜索

//本人新手，代码写得有些“丑”，请见谅，勿喷
#include<bits/stdc++.h>
using namespace std;
const long long int INF=0x7f7f7f7f;
long long int dx[]={-1,1,0,0},dy[]={0,0,-1,1},val[105][105];
long long int r,c,x,y,head,tail,tx,ty,sum,maxn=INF;//到终点的路不止一条，要进行比较
char a[105][105];
struct node
{
long long int x,y,sum;
}q[1000005];
int main()
{
memset(val,0x7f,sizeof(val));//求最小初始化全为最大
cin>>r>>c;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
cin>>a[i][j];
if(a[i][j]'Z')//将起点入队
{
q[1]={i,j,0};
val[i][j]=0;
}
if(a[i][j]'W')
{
x=i;
y=j;
}
}
if(q[1].xx&&q[1].yy)//要加特判，终点和起点在同一位置，输出0
{
cout<<0;
return 0;
}
head=0;
tail=1;
while(head<tail)
{
head++;
x=q[head].x;
y=q[head].y;
for(int i=0;i<4;i++)//枚举4个方向
{
tx=x+dx[i];//计算新位置
ty=y+dy[i];
if(tx>=1&&tx<=r&&ty>=1&&ty<=c)//不越界
{
if(a[tx][ty]'#')//如果是墙
continue;
if(a[tx][ty]>='0'&&a[tx][ty]<='9')
sum=q[head].sum+1+(a[tx][ty]-'0');//计算当前位置的最短时间
else
sum=q[head].sum+1;
if(sum<val[tx][ty])//求最短
{
tail++;
q[tail]={tx,ty,sum};
val[tx][ty]=sum;
if(a[tx][ty]'W')//如果是终点
maxn=min(maxn,q[tail].sum);//求出到终点的最少时长
}
}
}
}
if(maxn==INF)//如果此变量的值未变，就说明并未到达终点
cout<<"IMPOSSIBLE";
else
cout<<maxn;
return 0;
}