题意
给你一个N*M的地图(N,M<=20),地图上’#’表示障碍物，’B’表示炸弹，数字表示宝藏序号（宝藏+炸弹个数 <=8），每个宝藏有价值（-200<=v<=200），’S’表示出发点。每次移动可以从一个格子移动到相邻格子(上下左右)。寻找一条路径从’S’出发再回到’S’的封闭路径，移动步数记为K，这个路径所包围的宝藏价值总和记为V，则这条路径的价值为V-K。题目即是求可行的最大的路径价值，并且不能包围炸弹。
题解
可以将炸弹转化为v=-1600的宝藏，这样可确保选不到炸弹。
状压一下选的宝藏，之后便可以跑dp。
那么怎么确定选中了哪些宝藏呢？可以运用射线法（很好理解、但之前不知道0.0）。
射线法
可以从点向任意方向发出一条射线，判断与这个多边形的交点数量的奇偶性，奇数则在内，偶数则在外。但要注意一下与顶点相交时的判断。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
bool can[30][30];
int sx,sy;
struct state{
int x,y,st;
};
int x[10],y[10],w[10],mp[10];int tot=0;
int bx[10],by[10];int btot=0;
int dp[30][30][256];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int sum[256];
int main(){
scanf("%d %d\n",&n,&m);
char ch;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%c",&ch);
switch(ch){
case '.':
case 'S':
can[i][j]=1;break;
default:
can[i][j]=0;
}
switch(ch){
case '#':
case '.': break;
case 'S':
sx=i;sy=j;break;
case 'B':
bx[++btot]=i;
by[btot]=j;
break;
default:
x[++tot]=i;
y[tot]=j;
mp[ch-'1'+1]=tot;
break;
}
}
scanf("\n");
}
for(int i=1;i<=tot;++i){
scanf("%d",&w[mp[i]]);
}
for(int i=1;i<=btot;++i){
x[++tot]=bx[i];
y[tot]=by[i];
w[tot]=-3000;
}
for(int i=1;i<(1<<tot);++i){
for(int j=0;j<tot;++j){
if(i&(1<<j))sum[i]+=w[j+1];
}
}
memset(dp,0xff,sizeof dp);
dp[sx][sy][0]=0;
queue<state> q;，
q.push({sx,sy,0});
int ans=0;
while(q.size()){
state u = q.front();q.pop();
if(u.x==sx&&u.y==sy){
ans=max(ans,sum[u.st]-dp[u.x][u.y][u.st]);
}
for(int i=0;i<4;++i){
int tx=u.x+dx[i],ty=u.y+dy[i];
if(tx<1||tx>n||ty<1||ty>m)continue;
if(!can[tx][ty])continue;
int nst=u.st;
for(int j=1;j<=tot;++j){
if ((x[j]==tx&&u.x<tx&&y[j]<ty) //相当于是向右边发射了一条射线，nst就表示了奇偶性
|| (x[j]==u.x&&u.x>tx&&y[j]<u.y))nst^=1<<(j-1);
}
if(!(~dp[tx][ty][nst])){
dp[tx][ty][nst]=dp[u.x][u.y][u.st]+1;
q.push({tx,ty,nst});
}
}
}
printf("%d",ans);
}