题解 P2337 【[SCOI2012]喵星人的入侵】
弓虽太弱
·
·
题解
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10,maxm=25;
int n,m,L,now,last,ans;
char map[maxm][maxm]; bool xxx[maxm][maxm];
void init()
{
scanf("%d%d%d",&n,&m,&L);
for (int i=1;i<=n;++i)
scanf("%s",map[i]+1);
if (n<m)
{
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (!xxx[i][j])
{
xxx[i][j]=xxx[j][i]=1;
swap(map[i][j],map[j][i]);
}
swap(n,m);
}
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (map[i][j]=='T')
map[i][j]='S';
}
struct Tp{
int s1,s2,v;
};
struct Tsp
{
static const int mod=15271,maxm=10000,Index=(int)(1e9+7);
int now[mod],pre[maxm],tot; Tp f[maxm];
void clear()
{
memset(now,0,sizeof(now));
tot=0;
}
int find(Tp a)
{
int tmp=(1LL*a.s1*Index+a.s2)%mod;
for (int p=now[tmp];p;p=pre[p])
if (f[p].s1==a.s1 && f[p].s2==a.s2)
{
if (a.v>f[p].v)
f[p].v=a.v;
return f[p].v;
}
pre[++tot]=now[tmp];
now[tmp]=tot;
f[tot].s1=a.s1;
f[tot].s2=a.s2;
return f[tot].v=a.v;
}
}f[2][21][7];
void addstate(int x,int y,Tp a)
{
f[now][x][y].find(a);
}
int cont1[maxn],cont2[maxn];
void decode(Tp a)
{
for (int i=m+1;i>=1;--i)
cont1[i]=a.s1&3,a.s1>>=2;
for (int i=m+1;i>=1;--i)
cont2[i]=a.s2&3,a.s2>>=2;
}
Tp encode(int v)
{
Tp a;
a.v=v;
a.s1=0;
a.s2=0;
for (int i=1;i<=m+1;++i)
a.s1=(a.s1<<2)+cont1[i];
for (int i=1;i<=m+1;++i)
a.s2=(a.s2<<2)+cont2[i];
return a;
}
int findr(int res,int x)
{
for (;;++x)
if (cont1[x]==1 || cont1[x]==2)
{
if (cont1[x]==1)
++res;
else
--res;
if (!res)
return x;
}
}
int findl(int res,int x)
{
for (;;--x)
if (cont1[x]==1 || cont1[x]==2)
{
if (cont1[x]==1)
++res;
else
--res;
if (!res)
return x;
}
}
int find(int a,int x)
{
if (a==1)
return findr(1,x+1);
return findl(-1,x-1);
}
void expand(int x,int y,Tp a)
{
decode(a);
int north=cont1[y],west=cont1[m+1],nw=cont2[m+1];
if (y==1 && west)
return ;
if (y==1)
nw=0;
cont2[m+1]=cont2[y];
int sum=0;
for (int i=1;i<=m+1;++i)
if (cont1[i]==3)
++sum;
int ad=0;
if (y>1 && cont2[y-1]==2)
++ad;
if (nw==2)
++ad;
if (cont2[y]==2)
++ad;
if (y<m && cont2[y+1]==2)
++ad;
if (map[x][y]=='.')
{
if ((y==1 || west || cont2[y-1]!=1) && (x==1 || north || cont2[y]!=1))
{
cont2[y]=1;
if (west && north)
{
if (west==north)
{
if (west==3)
{
cont1[y]=0;
cont1[m+1]=0;
addstate(x,y,encode(a.v+ad));
}
else
{
cont1[find(west,y)]=west;
cont1[y]=0;
cont1[m+1]=0;
addstate(x,y,encode(a.v+ad));
}
}
else if (west==3 || north==3)
{
cont1[find(min(west,north),y)]=3;
cont1[y]=0;
cont1[m+1]=0;
addstate(x,y,encode(a.v+ad));
}
else if (west==2 && north==1)
{
cont1[y]=0;
cont1[m+1]=0;
addstate(x,y,encode(a.v+ad));
}
}
else if (west && !north)
{
cont1[y]=0;
cont1[m+1]=west;
addstate(x,y,encode(a.v+ad));
cont1[y]=west;
cont1[m+1]=0;
addstate(x,y,encode(a.v+ad));
}
else if (!west && north)
{
cont1[y]=0;
cont1[m+1]=north;
addstate(x,y,encode(a.v+ad));
cont1[y]=north;
cont1[m+1]=0;
addstate(x,y,encode(a.v+ad));
}
else if (!west && !north)
{
cont1[y]=1;
cont1[m+1]=2;
addstate(x,y,encode(a.v+ad));
}
}
}
if (map[x][y]=='S')
{
if ((y==1 || west || cont2[y-1]!=1) && (x==1 || north || cont2[y]!=1))
{
cont2[y]=1;
if ((west && !north) || (!west && north))
{
if (max(west,north)==3)
{
cont1[y]=0;
cont1[m+1]=0;
addstate(x,y,encode(a.v+ad));
}
else if (sum<=1)
{
cont1[find(max(west,north),y)]=3;
cont1[y]=0;
cont1[m+1]=0;
addstate(x,y,encode(a.v+ad));
}
}
if (!west && !north && sum<=1)
{
cont1[y]=0;
cont1[m+1]=3;
addstate(x,y,encode(a.v+ad));
cont1[y]=3;
cont1[m+1]=0;
addstate(x,y,encode(a.v+ad));
}
}
}
if (map[x][y]!='S')
{
if (!west && !north)
{
if (map[x][y]=='.')
decode(a),cont2[m+1]=cont2[y];
cont2[y]=0;
cont1[y]=0;
cont1[m+1]=0;
addstate(x,y,encode(a.v));
}
}
}
void expand_pt(int x,int y,Tp a)
{
decode(a);
int north=cont1[y],west=cont1[m+1],nw=cont2[m+1];
if (north || west || map[x][y]!='.')
return;
if (y==1)
nw=0;
int ad=0;
if (y>0 && cont2[y-1]==1)
++ad;
if (nw==1)
++ad;
if (cont2[y]==1)
++ad;
if (y<m && cont2[y+1]==1)
++ad;
cont2[m+1]=cont2[y];
cont2[y]=2;
addstate(x,y,encode(a.v+ad));
}
void clearf(int x)
{
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
f[x][i][j].clear();
}
void work()
{
now=0,last=1;
clearf(now);
Tsp *x;
for (int l=0;l<=L;++l)
{
addstate(0,0,(Tp){0,0,0});
x=&f[now][0][0];
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
{
for (int k=1;k<=x->tot;++k)
expand(i,j,x->f[k]);
x=&f[now][i][j];
}
swap(now,last); clearf(now);
if (l!=L)
{
x=&f[last][0][0];
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
{
for (int k=1;k<=x->tot;++k)
expand_pt(i,j,x->f[k]);
x=&f[last][i][j];
}
}
for (int k=1;k<=x->tot;++k)
if (x->f[k].s1==0 && x->f[k].v>ans)
ans=x->f[k].v;
}
printf("%d\n",ans);
}
int main()
{
init();
work();
return 0;
}