about 4 years ago

终于发现了自己的手残
因为范围不大所以用搜索来转移状态。
转移的时候用了射线法

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
struct node{int x,y,num;};
queue<node> q;
int f[12][12][1<<11],n,m,d,ans=0,a[12],v[1<<11],pos[12][2];
char map[12][12];
const int dx[4]={-1,0,0,1};
const int dy[4]={0,-1,1,0};
int calc(int num,int x,int y,int xx)
{
    for (int i=1;i<=d;i++)
        if (pos[i][1]>y&&(x==pos[i][0]&&xx>pos[i][0]||xx==pos[i][0]&&x>pos[i][0]))   num=num^(1<<i-1);
    return num;
}
int get(int st,int x,int y,int xx)
{
    for(int i=1;i<=d;i++)
        if(y<pos[i][1]&&(x==pos[i][0]&&xx>pos[i][0]||x>pos[i][0]&&xx==pos[i][0]))
            st^=1<<i-1;
    return st;
}
void search(int x,int y)
{
    int i,xx,yy,num;
    memset(f,-1,sizeof(f));
    q.push((node){x,y,0} );f[x][y][0]=0; 
    while (!q.empty())
    {
        node temp=q.front();q.pop();
        for (i=0;i<4;i++)
        {
            xx=temp.x+dx[i];yy=temp.y+dy[i];
            if (xx<=n&&xx>=1&&yy<=m&&yy>=1&&map[xx][yy]=='0')
            {
                num=get(temp.num,temp.x,temp.y,xx);
                if (f[xx][yy][num]==-1)
                {
                    f[xx][yy][num]=f[temp.x][temp.y][temp.num]+1;
                    q.push((node){xx,yy,num});
                }
            } 
        }
    }
    for (i=1;i<(1<<d);i++)   if (f[x][y][i]!=-1) ans=max(ans,v[i]-f[x][y][i]);
}
int main()
{
    int i,j,posn=0,k;
    scanf("%d%d%d",&n,&m,&d);
    for (i=1;i<=d;i++) scanf("%d",&a[i]);
    for (i=1;i<(1<<d);i++)   for (j=i,k=1;k<=d;k++)   if (j&(1<<k-1))    v[i]+=a[k];
    for (i=1;i<=n;i++)
        {
            scanf("%s",map[i]+1);
            for (j=1;j<=m;j++)
                if (map[i][j]!='0'&&map[i][j]!='#')   pos[map[i][j]-'0'][0]=i,pos[map[i][j]-'0'][1]=j;
        }
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)   if(map[i][j]=='0')    search(i,j);
    printf("%d\n",ans);
}
← 【bzoj1020】【神剪枝】【二分】【几何新技能】安全的航线 【bzoj1951】【数论集合】古代猪文 →
 
comments powered by Disqus