解题报告

题目里已经告诉我们怎么判断宝藏和陷阱是否被圈起来了……由于只和奇偶性有关，所以可以状压：

$f_{x,y,A,B}$ 表示目前在 $(x,y)$ ，宝藏的状态是 $A$ ，陷阱的状态是 $B$ 的最少步数。

是的……他就是个BFS……连DP都不算……

示例程序

射线法判断的时候可以强制一个方向（比如往上），并且忽略掉同方向的路径。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=20,maxk=8,maxt=26214400,dif[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int n,m,X,Y,f[maxn+5][maxn+5][1<<maxk][1<<maxk],ans;char pic[maxn+5][maxn+5];
int A,B,num[maxk+5],val[1<<maxk];pair<int,int> a[maxk+5],b[maxk+5];
struct data {int x,y,sa,sb;} que[maxt+5];

#define check(x,y) (1<=(x)&&(x)<=n&&1<=(y)&&(y)<=m&&pic[x][y]=='.')
inline bool Fmin(int &x,int y) {return y<x?(x=y,true):false;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%s",pic[i]+1);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            if (pic[i][j]=='S') X=i,Y=j,pic[i][j]='.'; else if (pic[i][j]=='B') b[B++]=mp(i,j);
            else if (isdigit(pic[i][j])) A++,a[pic[i][j]-'1']=mp(i,j);
        }
    for (int i=0;i<A;i++) scanf("%d",&num[i]);memset(f,63,sizeof(f));f[X][Y][0][0]=0;
    int Head=0,Tail=0;que[++Tail]=(data){X,Y,0,0};
    while (Head!=Tail){
        data now=que[++Head];int x=now.x,y=now.y,sa=now.sa,sb=now.sb;
        for (int t=0;t<4;t++){
            int xx=x+dif[t][0],yy=y+dif[t][1],ta=sa,tb=sb;if (!check(xx,yy)) continue;
            if (t==1||t==3){
                for (int i=0;i<A;i++) if (a[i].fr>x&&(t==1&&a[i].sc==yy||t==3&&a[i].sc==y)) ta^=1<<i;
                for (int i=0;i<B;i++) if (b[i].fr>x&&(t==1&&b[i].sc==yy||t==3&&b[i].sc==y)) tb^=1<<i;
            }if (Fmin(f[xx][yy][ta][tb],f[x][y][sa][sb]+1)) que[++Tail]=(data){xx,yy,ta,tb};
        }
    }for (int i=0;i<(1<<A);i++) for (int j=0;j<A;j++) if (i>>j&1) val[i]+=num[j];
    for (int i=0;i<(1<<A);i++) ans=max(ans,val[i]-f[X][Y][i][0]);printf("%d\n",ans);return 0;
}