SOL：
BFS式dp。
#include<bits/stdc++.h> using namespace std; struct state{int x,y,z;state(){}state(int _x,int _y,int _z):x(_x),y(_y),z(_z){}}X; queue<state> Q; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; int x,y,anw,sp,sta[18],ans,f[23][23][1<<8|1],n,m,p[23][23],val[18],px,ox[18],oy[18],xoxo; char s[27][27]; void sol(int i) { anw=0; for (int j=0;j<sp;j++) if ((i>>j)&1) {if (sta[j]==-1) return; anw+=val[sta[j]]; } ans=max(ans,anw-f[x][y][i]); } void dowork() { for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (s[i][j]=='B'||isdigit(s[i][j])) (sta[sp]=(isdigit(s[i][j])?px++,s[i][j]-48:-1)),ox[sp]=i,oy[sp++]=j; else if (s[i][j]=='S') x=i,y=j; for (int i=1;i<=px;i++) scanf("%d",val+i); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=0;k<sp;k++) if (i<ox[k]&&j==oy[k]) p[i][j]|=1<<k; } int top; signed main () { // freopen("2.in","r",stdin); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%s",s[i]+1); dowork(); memset(f,127,sizeof f); f[x][y][0]=0; Q.push(state(x,y,0)); while (!Q.empty()) { X=Q.front(); Q.pop(); // if (X.x==5&&X.y==1&&X.z==13) { // top=0; // } // cout<<X.x<<' '<<X.y<<' '<<X.z<<endl; for (int i=0;i<4;i++) { int nx=X.x+dx[i], ny=X.y+dy[i]; if (s[nx][ny]!='.'&&s[nx][ny]!='S') continue; if (nx<1||nx>n||ny<1||ny>m) continue; xoxo=X.z; if (i==1) xoxo=X.z^p[X.x][X.y]; if (i==3) xoxo=X.z^p[nx][ny]; if (f[nx][ny][xoxo]>f[X.x][X.y][X.z]+1) { f[nx][ny][xoxo]=f[X.x][X.y][X.z]+1; Q.push(state(nx,ny,xoxo)); // if (++top<30) cout<<"exd"<<nx<<' '<<ny<<' '<<xoxo<<endl; } } } for (int i=0;i<(1<<sp);i++) sol(i); printf("%d ",ans); }