[BZOJ1294][SCOI2009]围豆豆Bean 射线法+状压dp+spfa

1294: [SCOI2009]围豆豆Bean

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 458  Solved: 305
[Submit][Status][Discuss]

Description

Input

第一行两个整数N和M，为矩阵的边长。 第二行一个整数D，为豆子的总个数。 第三行包含D个整数V1到VD，分别为每颗豆子的分值。 接着N行有一个N×M的字符矩阵来描述游戏矩阵状态，0表示空格，#表示障碍物。而数字1到9分别表示对应编号的豆子。

Output

仅包含一个整数，为最高可能获得的分值。

Sample Input

3 8
3
30 -100 30
00000000
010203#0
00000000

Sample Output

38

HINT

50%的数据满足1≤D≤3。
100%的数据满足1≤D≤9，1≤N, M≤10，-10000≤Vi≤10000。

从每个豆豆射出一条射线，若经过路线奇数次则说明路线将其包围，若经过偶数次则不包围。

设状态f[i][j][k]表示到达（i，j）围豆豆状态为k的最大价值。

每次枚举起点，用spfa转移即可。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #define maxn 15

 using namespace std;

 int tx[]={,-,,};

 int ty[]={,,,-};

 char a[maxn];

 int num[maxn][maxn];

 int val[maxn];

 int n,m,d;

 int x[maxn],y[maxn];

 int f[maxn][maxn][];

 int inq[maxn][maxn][];

 int ans=;

 struct data {

     int x,y,z;

 }q[];

 void work(int i,int j) {

     memset(f,-,sizeof(f));

     int head=,tail=;

     q[]=(data){i,j,};

     f[i][j][]=;

     while(head!=tail) {

         data now=q[head++];if(head==) head=;

         if(now.x==i&&now.y==j) ans=max(ans,f[now.x][now.y][now.z]);

         for(int k=;k<;k++) {

             int tox=now.x+tx[k],toy=now.y+ty[k],toz=now.z;

             int add=;

             if(tox<||toy<||tox>n||toy>m||num[tox][toy]!=) continue;

             if(now.x!=tox) {

                 data temp;

                 if(tox>now.x) temp=(data){now.x,now.y,now.z};else temp=(data){tox,toy,now.z};

                 for(int l=;l<=d;l++) {

                     if(temp.y>y[l]&&temp.x==x[l]) {

                         temp.z^=(<<(l-));

                         if(temp.z&(<<(l-))) add+=val[l];

                         else add-=val[l];

                     }

                 }

                 toz=temp.z;

             }

             if(f[tox][toy][toz]<f[now.x][now.y][now.z]+add-){

                 f[tox][toy][toz]=f[now.x][now.y][now.z]+add-;

                 if(!inq[tox][toy][toz]) {

                     q[tail++]=(data){tox,toy,toz};if(tail==) tail=;

                     inq[tox][toy][toz]=;

                 }

             }

             inq[now.x][now.y][now.z]=;

         }

     }

 }

 int main() {

     scanf("%d%d%d",&n,&m,&d);

     for(int i=;i<=d;i++) scanf("%d",&val[i]);

     for(int i=;i<=n;i++) {

         scanf("%s",a+);

         for(int j=;j<=m;j++) {

             if(a[j]=='') num[i][j]=;

             else if(a[j]!='#') x[a[j]-'']=i,y[a[j]-'']=j,num[i][j]=-;

             else num[i][j]=;

         }

     }

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             if(num[i][j]==) work(i,j);

     printf("%d",ans);

     return ;

 }