Description
你有一个长方形的地图，每一个格子要么是一个障碍物，要么是一个有一定价值的宝藏，要么是一个炸弹，或者是一块空地。你的初始位置已经给出。
你每次可以走到上、下、左、右这四个相邻的格子。你不允许走出这幅地图，不允许进入有宝藏、障碍物或是炸弹的地方。你需要规划一个闭合的路线（起点和终点都必须在初始位置）来取得宝藏。注意这个路线围成的多边形中不可以包含炸弹。假设路线围成的多边形包含的所有宝藏的价值之和为v,并且你从起点到终点走了 k步（从一个格子走到旁边的格子算作一步），那么你沿该路线走一次将可以获得v-k的利润。
你的任务是规划一个不包含炸弹的闭合路线，并可获得最大的利润。
注意路线可以自交。为了确定一个格子是否在这条路线里面，请使用以下算法判断：
1.假设该点的坐标为需要判断的点为 p(i,j) ，该点不在路线上
2.从该点往任意方向作一条射线，如果与路线相交奇数次，我们就认为这个格子在这条路线里面，否则这个格子在这条路线外面。
n,m<=20。炸弹和宝藏的个数总和不超过8个，保证只有1个初始点。
Solution
本题难点其实就是判断格子是否在路线里面。（题目好良心系列）我选定的射线方向是竖直向上（当然其他方向也ok呀）。
所以，如果画出路径，所有的射线只会和横向路径相交（竖向的路径就直接忽略啦）
对于每一小段横向路径（即点(x,y)到(x,y+1)），我们记录这一小段路径的右端点。如此以保证奇偶性正确。
5 — 4 —3
| |
6 9 2
| |
7 — 8 — 1
如图，我们沿1-8寻找回路，则被记录的点有3,4,8,1。
虽然5和7没有被记录到，但这不影响9（多边形内部）和多边形外部的点的判断。
(当然，如果是记录所有横向路径的点也可以，例如记3,4,5,7,8,1;不过这就需要加些特判了）
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=,K=;
int f[][]={{,},{,-},{,},{-,}};
int tx[],ty[],cnt,k;
int n,m,sx,sy,w[];
char mp[][];
int dp[][][<<K];
int q[**(<<K)],l,r;
int num(int x,int y,int z){return x*N*(<<K)+y*(<<K)+z;}
int getx(int c){return c/(N*(<<K));}
int gety(int c){return c/(<<K)%N;}
int getz(int c){return c%(<<K);}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
{
scanf("%s",mp[i]+);
for (int j=;j<=m;j++) if (mp[i][j]=='S'){mp[i][j]='.';sx=i;sy=j;}
else if (mp[i][j]>''&&mp[i][j]<'')
{tx[mp[i][j]-'']=i;ty[mp[i][j]-'']=j;cnt++;mp[i][j]='#';}
} k=cnt;
for (int i=;i<=n;i++) for (int j=;j<=m;j++)
if (mp[i][j]=='B')
{mp[i][j]='#';tx[cnt]=i;ty[cnt]=j;cnt++;}
for (int i=;i<k;i++) scanf("%d",&w[i]); memset(dp,0x3f,sizeof(dp));
dp[sx][sy][]=;
q[]=num(sx,sy,);
l=r=;
int _x,_y,_z,zz;
while (l<=r)
{
_x=getx(q[l]);_y=gety(q[l]);_z=getz(q[l]);l++;
for (int i=;i<;i++)
{
if (_x+f[i][]<=n&&_x+f[i][]&&_y+f[i][]&&_y+f[i][]<=m&&mp[_x+f[i][]][_y+f[i][]]=='.')
{
zz=_z;
if (!i) for (int j=;j<cnt;j++) if (tx[j]>_x&&ty[j]==_y) zz^=<<j;
if (i==)
for (int j=;j<cnt;j++) if (tx[j]>_x+f[i][]&&ty[j]==_y+f[i][]) zz^=<<j;
if (dp[_x][_y][_z]+<dp[_x+f[i][]][_y+f[i][]][zz])
{
dp[_x+f[i][]][_y+f[i][]][zz]=dp[_x][_y][_z]+;
q[++r]=num(_x+f[i][],_y+f[i][],zz);
}
}
}
}
bool _is;int ans=,sum,t;
for (int i=;i<<<cnt;i++)
{
sum=;_is=;
for (int j=;j<cnt;j++)
{
t=i&(<<j);
if (j>=k&&t) _is=;
if (j<k&&t) sum+=w[j];
}
if (_is) ans=max(ans,sum-dp[sx][sy][i]);
}
cout<<ans;
}