题解

#include<iostream>
#include<cmath>
using namespace std;
int n,m,sx,sy,ex,ey,ans=1e9,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
char a[30][30];
bool flag[30][30];
void f(int x,int y,int sum){
    if(x==ex&&y==ey){
        ans=min(ans,sum);
        return;
    }
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&flag[nx][ny]==0&&a[nx][ny]!='#'){
            flag[nx][ny]=1;
            if(a[nx][ny]>='1'&&a[nx][ny]<='9'){
                f(nx,ny,sum+a[nx][ny]-'0'+1);
            }else{
                f(nx,ny,sum+1);
            }
            flag[nx][ny]=0;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='Z'){
                sx=i;
                sy=j;
            }else if(a[i][j]=='W'){
                ex=i;
                ey=j;
            }
        }
    }
    flag[sx][sy]=1;
    f(sx,sy,0);
    if(ans==1e9){
        cout<<"IMPOSSIBLE";
    }else{
        cout<<ans;
    }
    return 0;
}