BZOJ 1294 [SCOI2009]围豆豆Bean

本文主要是介绍BZOJ 1294 [SCOI2009]围豆豆Bean，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

Sample Output

HINT

50%的数据满足1≤D≤3。

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

这个题呀，好题。

可以边搜索边更新状态，用射线法（自己百度吧）。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,d,ans,v[11],mp[11][11],x[11],y[11],dis[1105][11][11];
bool inq[1105][11][11];
int xx[]={-1,0,1,0},yy[]={0,-1,0,1};
struct node
{int x,y,z;//x,y坐标，z吃豆子的情况 
};
queue<node>q;
void bfs(int sx,int sy)
{memset(dis,0x3f,sizeof(dis));memset(inq,0,sizeof(inq));node t;dis[0][sx][sy]=0;t.x=sx,t.y=sy,t.z=0;q.push(t);inq[0][sx][sy]=1;while(!q.empty()){node u=q.front();q.pop();inq[u.z][u.x][u.y]=0;for(int i=0;i<=3;i++)if(u.x+xx[i]>=1&&u.x+xx[i]<=n&&u.y+yy[i]>=1&&u.y+yy[i]<=m&&mp[u.x+xx[i]][u.y+yy[i]]==0){t.x=u.x+xx[i],t.y=u.y+yy[i],t.z=u.z;for(int j=1;j<=d;j++)if(t.y>y[j]&&((u.x>x[j]&&t.x<=x[j])||(u.x<=x[j]&&t.x>x[j])))//垂直于x轴的射线 t.z^=(1<<(j-1));if(dis[t.z][t.x][t.y]>dis[u.z][u.x][u.y]+1){dis[t.z][t.x][t.y]=dis[u.z][u.x][u.y]+1;if(!inq[t.z][t.x][t.y]){inq[t.z][t.x][t.y]=1;q.push(t);}}}}int end=(1<<d)-1;for(int i=1;i<=end;i++){int tmp=-dis[i][sx][sy];for(int j=1;j<=d;j++)if(i&(1<<(j-1)))tmp+=v[j];ans=max(tmp,ans);}
}
int main()
{scanf("%d%d%d",&n,&m,&d);for(int i=1;i<=d;i++)scanf("%d",&v[i]);for(int i=1;i<=n;i++){char s[15];scanf("%s",s+1);for(int j=1;j<=m;j++)if(s[j]=='#')mp[i][j]=1;else if(s[j]=='0')mp[i][j]=0;else{mp[i][j]=1;x[s[j]-'0']=i;y[s[j]-'0']=j;}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]==0)bfs(i,j);printf("%d\n",ans);return 0;
}

这篇关于BZOJ 1294 [SCOI2009]围豆豆Bean的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---