Description

[SCOI2009]围豆豆-LMLPHP

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。

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

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

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

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

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

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

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

如下图所示:

[SCOI2009]围豆豆-LMLPHP

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

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

 #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;
}
05-02 22:02