【DP】【BFS】[JZOJ4389] 圈地游戏

Description

Solution

题面已经给出了如何判定一个格子有没有被圈住。不妨规定我们的判定射线就是竖直向上
设状态F[i][j][S]$F[i][j][S]$表示当前在(i,j)$(i,j)$这个点，S为关键点（宝藏和陷阱）判定射线上路径经过次数的奇偶二进制状态。

DP状态设出来用BFS转移即可

注意可能会出现共线的情况，于是我们规定，向上向下走不更新奇偶性，向右走的话算这一步的起点，向左走算这一步的终点，这样就有效保证了正确性。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 22
#define M 258
using namespace std;
int n,m,d[3*N*N*M][3],f[N][N][M],vl[N],a1[N][3],li,t,sx,sy,cf[9],fx[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
bool map[N][N];
void bfs()
{
    int l=0,r=1;
    d[1][0]=sx,d[1][1]=sy,d[1][2]=0;
    memset(f,107,sizeof(f));
    f[sx][sy][0]=0;
    while(l<r)
    {
        int x=d[++l][0],y=d[l][1],s=d[l][2];
        fo(k,0,3)
        {
            int p=x+fx[k][0],q=y+fx[k][1],s1=s;
            if(p<1||q<1||p>n||q>m||map[p][q]) continue;
            if(k<2)
            {
                fo(i,1,li)
                {
                    if(a1[i][0]>p)
                    {
                        if(k==1&&a1[i][1]==y) s1^=cf[i-1];
                        if(k==0&&a1[i][1]==q) s1^=cf[i-1]; 
                    }
                }
            }
            if(f[p][q][s1]>f[x][y][s]+1)
            {
                if(f[p][q][s1]==1802201963) d[++r][0]=p,d[r][1]=q,d[r][2]=s1;
                f[p][q][s1]=f[x][y][s]+1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    cf[0]=1;
    fo(i,1,8) cf[i]=cf[i-1]*2;
    fo(i,1,n)
    {
        scanf("\n");
        fo(j,1,m)
        {
            char ch=getchar();
            if('0'<=ch&&ch<='9') a1[++li][0]=i,a1[li][1]=j,a1[li][2]=ch-'0',map[i][j]=1,t++;
            if(ch=='B') a1[++li][0]=i,a1[li][1]=j,a1[li][2]=-1,map[i][j]=1;
            if(ch=='#') map[i][j]=1;
            if(ch=='S') sx=i,sy=j;
        }
    }
    fo(i,1,t) scanf("%d",&vl[i]);
    bfs();
    int ans=0;
    fo(j,0,cf[li]-1)
    {
        int s=0;
        fo(i,1,li) 
        {
            if(a1[i][2]==-1&&(j&cf[i-1])>0) {s=-1;break;}
            if(a1[i][2]>0&&(j&cf[i-1])>0) s+=vl[a1[i][2]]; 
        }
        if(s>0) ans=max(ans,s-f[sx][sy][j]);
    }
    printf("%d\n",ans);
}