[SCOI2009]围豆豆

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

HINT

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

这个博客有详细图片和解析

http://blog.csdn.net/Phenix_2015/article/details/50739989

问题在于如何判断一个豆子是否在多边形内。

实际上有一个很好判断的方法，那就是可以引一条水平射线，看和多边形有几个交点，有奇数个交点就在多边形内，否则在多边形外。

这样状态压缩，对于一个状态，肯定步数越少越好，然后就可以更据压缩的状态，做分层图最短路

每走一步就可以更新当前状态

但还有一种情况，在偶数个交点时也有可能被围起来。

如下图所示：

那么转移的过程中，显然水平方向的移动是不影响答案的，只有竖直方向的移动才会影响到点的位置

特殊情况把每一条线段假设成上端为开下端为闭的线段，即只有下断点与射线相交才会有用，那么这样同向的线段就只会被算一次了

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 using namespace std;

 struct ZYYS

 {

   int x,y,s;

 };

 const int dx[]={,,,-};

 const int dy[]={,-,,};

 int d,px[],py[],n,m,val[],ans;

 int dist[][][],inf;

 bool vis[][][];

 char ss[][];

 int cross(int sx,int sy,int x,int y,int s)

 {int i;

   int p=max(sy,y);

   for (i=;i<=d;i++)

     if (py[i]==p&&px[i]<x)

       s^=(<<i-);

   return s;

 }

 void spfa(int sx,int sy)

 {int i,j;

   queue<ZYYS>Q;

   memset(dist,/,sizeof(dist));

   inf=dist[][][];

   memset(vis,,sizeof(vis));

   Q.push((ZYYS){sx,sy,});

   dist[sx][sy][]=;

   while (Q.empty()==)

     {

       ZYYS u=Q.front();

       Q.pop();

       vis[u.x][u.y][u.s]=;

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

     {

       int x=u.x+dx[i],y=u.y+dy[i];

       if (x<||x>n||y<||y>m) continue;

       if (ss[x][y]=='#'||ss[x][y]!='') continue;

       int s=u.s;

       if (i<=)

         s=cross(u.x,u.y,x,y,s);

       if (dist[x][y][s]>dist[u.x][u.y][u.s]+)

         {

           dist[x][y][s]=dist[u.x][u.y][u.s]+;

           if (vis[x][y][s]==)

         {

           vis[x][y][s]=;

           Q.push((ZYYS){x,y,s});

         }

         }

     }

     }

   for (i=;i<=(<<d)-;i++)

     {

       int res=-dist[sx][sy][i];

       for (j=;j<=d;j++)

     if (i&(<<j-)) res+=val[j];

       ans=max(ans,res);

     }

 }

 int main()

 {int i,j;

   cin>>n>>m>>d;

   for (i=;i<=d;i++)

     {

       scanf("%d",&val[i]);

     }

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

     {

       scanf("%s",ss[i]+);

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

     {

       if (ss[i][j]>''&&ss[i][j]<='')

         px[ss[i][j]-'']=i,py[ss[i][j]-'']=j;

     }

     }

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

     {

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

     if (ss[i][j]=='')

     {

       spfa(i,j);

     }

     }

   cout<<ans;

 }

秒客网