【SCOI2009】bzoj1294 围豆豆

暴力bfs显然不可行，需要判重。虽然状态有无穷多个，但是我们只关心哪些豆子被包围以及目前的步数。为了方便从每个豆子向上偏右引一条射线，记下多边形穿过射线次数的奇偶性，就可以表示豆子被包围的情况。
这样，记状态$(x,y,s)$表示当前在点$(x,y)$，被奇数次穿过的豆子为集合$s$，每走一步枚举豆子进行更新，复杂度$O(m^2n^22^dd)$。好像可以预处理去掉一个$O(d)$。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
char mp[15][15];
int last[12][12][600],px[10],py[10],v[10],
qx[2000010],qy[2000010],qs[2000010],qans[2000010],
xx[]={
   1,-1,0,0},yy[]={
   0,0,1,-1},
n,m,d,clo;
int ok(int x,int y)
{return x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]=='0';
}
int main()
{int hd,tl,x1,y1,s1,x,y,s,now,ans=0,tem;scanf("%d%d%d",&n,&m,&d);for (int i=0;i<d;i++) scanf("%d",&v[i]);for (int i=1;i<=n;i++){scanf("%s",mp[i]+1);for (int j=1;j<=m;j++)if (mp[i][j]>='1'&&mp[i][j]<='9'){px[mp[i][j]-'1']=i;py[mp[i][j]-'1']=j;}}for (int sx=1;sx<=n;sx++)for (int sy=1;sy<=m;sy++)if (ok(sx,sy)){last[sx][sy][0]=++clo;qx[1]=sx;qy[1]=sy;qs[1]=qans[1]=0;hd=tl=1;while (hd<=tl){x=qx[hd];y=qy[hd];s=qs[hd];now=qans[hd++];if (x==sx&&y==sy){tem=-now;for (int i=0;i<d;i++)if (s&(1<<i)) tem+=v[i];ans=max(ans,tem);}for (int k=0;k<4;k++)if (ok(x1=x+xx[k],y1=y+yy[k])){s1=s;for (int i=0;i<d;i++)   if (y<py[i]&&((x==px[i]&&k==0)||(x==px[i]+1&&k==1)))s1^=1<<i;if (last[x1][y1][s1]<clo){last[x1][y1][s1]=clo;tl++;qx[tl]=x1;qy[tl]=y1;qs[tl]=s1;qans[tl]=now+1;}}}}printf("%d\n",ans);
}