题解 P3272 【[SCOI2011]地板】
广告
蒟蒻的blog
内有多道插头dp题目，配合使用口感更佳～
思路：
没学过插头dp的可以看这里
这个L形......第一眼看上去真的是丧病啊
但是仔细想想，实际上也就是拿一堆路径铺满一个棋盘，这个路径还是有限制的
那还有什么好说的，插头dp上啊【雾】
首先。我们定义这道题中的一个插头代表着从这个格子往插头指向的方向可以伸展一个L形
但是整张图上的所有插头不可能只有一种，因此我们要分析，可以继续延伸的L形都有哪些限制呢？
我们知道，L形的一个特点就是拐了一个弯，而且只拐了一个弯，因此我们可以定义这样的两种插头：
插头1代表一个还没有拐过弯的L形的延伸，插头2则代表一个已经拐过弯的L形的延伸
这样我们解决了定义问题，接下来看如何分类讨论
第一种情况：当前状态下，当前格子上方和左方都没有插头
这时我们需要找一个L形来把这个格子填上，那么我们可能有三种决策：
决策一：给这个格子加一个二号下插头和一个二号右插头，此时这个格子是一个新的L形的拐角
决策二：给这个格子加一个一号下插头，此时相当于构建了一个先向下再向右的L形，从当前格子开始
决策三：给这个格子加一个一号右插头，此时相当于构建了一个先向右再向下的L形，从当前格子开始
第二种情况：当前状态下，当前格子上方有一个一号下插头，左方没有插头
这时相当于上面有一个L形的未拐弯的一边伸过来了，有两种决策：
决策一：L形不拐弯，继续向下延伸，当前格子只有一个一号下插头
决策二：L形在当前格子拐弯，L形向右延伸，当前格子只有一个二号右插头
第三种情况：当前状态下，当前格子左方有一个一号右插头，上方没有插头
与第二种情况类似，故不赘述
第四种情况：当前状态下，当前格子上方有一个二号下插头，左方没有插头
这时相当于上面有一个L形的拐过弯的一边伸过来了，有两种决策：
决策一：L形继续延伸，当前格子有一个二号下插头
决策二：L形在当前格子终止，当前格子没有插头
决策二时注意，如果当前处在最后一个没有障碍的格子，那么需要统计入最终答案
第五种情况：当前状态下，当前格子左方有一个二号右插头，上方没有插头
与第四种情况类似，故不赘述
第六种情况：当前状态下，当前格子左方和上方都有一号插头
此时相当于两条“臂”伸了过来，在当前格子相交，应该合并成一个L形
当前格子相当于一个L形的拐弯处，没有插头
我们发现，情况一和情况六已经覆盖了四种L形的摆放方式，同时也不会有一个二号插头一个一号插头或者两个二号插头的情况出现——它们被上文的六种情况限制了
故这种分类讨论方式可以覆盖所有情况
状态可以用四进制表示（比较快），因为状态数较多，放到哈希表里面，滚动数组处理即可
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define hash deep_dark_fantasy
#define ll long long
#define MOD 20110520
using namespace std;
inline int read(){
int re=0,flag=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') flag=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*flag;
}
int n,m,x[150][150],cur,pre,ex,ey;
int st[2][300010];ll ans[2][300010],re;
int tot[2],bit[20],state[300010],st_tot,hash=300000;
struct edge{
int to,next;
}a[300010];
void insert(int now,ll val){
int p=now%hash;
for(int i=state[p];i;i=a[i].next){
if(st[cur][a[i].to]==now){
ans[cur][a[i].to]+=val;
ans[cur][a[i].to]%=MOD;return;
}
}
tot[cur]++;
a[++st_tot].to=tot[cur];
a[st_tot].next=state[p];
state[p]=st_tot;st[cur][tot[cur]]=now;ans[cur][tot[cur]]=val%MOD;
}
void dp(){
int i,j,k,down,right,now;ll val;
cur=0;tot[cur]=1;ans[cur][1]=1;st[cur][1]=0;
for(i=1;i<=n;i++){
for(j=1;j<=tot[cur];j++) st[cur][j]<<=2;
for(j=1;j<=m;j++){
memset(state,0,sizeof(state));st_tot=0;
pre=cur;cur^=1;tot[cur]=0;
for(k=1;k<=tot[pre];k++){
now=st[pre][k];val=ans[pre][k];
right=(now>>bit[j-1])%4;down=(now>>bit[j])%4;
if(!x[i][j]){//障碍格子
if(!down&&!right){
insert(now,val);continue;
}
}
if(!right&&!down){//第一种情况
if(x[i+1][j]&&x[i][j+1])
insert(now+((1<<bit[j-1])<<1)+((1<<bit[j])<<1),val);
if(x[i+1][j]) insert(now+(1<<bit[j-1]),val);
if(x[i][j+1]) insert(now+(1<<bit[j]),val);
}
if(right==1&&!down){//第三种情况
if(x[i][j+1]) insert(now-(1<<bit[j-1])+(1<<bit[j]),val);
if(x[i+1][j]) insert(now+(1<<bit[j-1]),val);
}
if(down==1&&!right){//第二种情况
if(x[i+1][j]) insert(now-(1<<bit[j])+(1<<bit[j-1]),val);
if(x[i][j+1]) insert(now+(1<<bit[j]),val);
}
if(right==2&&!down){//第五种情况
if(i==ex&&j==ey) re+=val,re%=MOD;
if(x[i][j+1]) insert(now-((1<<bit[j-1])<<1)+((1<<bit[j])<<1),val);
insert(now-((1<<bit[j-1])<<1),val);
}
if(down==2&&!right){//第四种情况
if(i==ex&&j==ey) re+=val,re%=MOD;
if(x[i+1][j]) insert(now-((1<<bit[j])<<1)+((1<<bit[j-1])<<1),val);
insert(now-((1<<bit[j])<<1),val);
}
if(down==1&&right==1){//第六种情况
if(i==ex&&j==ey) re+=val,re%=MOD;
insert(now-(1<<bit[j-1])-(1<<bit[j]),val);
}
}
}
}
}
int main(){//这道题的读入没有保证n>=m，所以我写了一个判断，来保证n>=m，具体操作就是把图旋转了九十度
int i,j;char ch;
n=read();m=read();
for(i=1;i<=20;i++) bit[i]=i<<1;
if(n>m){
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
ch=getchar();
while(ch!='*'&&ch!='_') ch=getchar();
x[i][j]=(ch=='_');
if(x[i][j]) ex=i,ey=j;
}
}
}
else{
swap(n,m);
for(i=m;i>0;i--){
for(j=1;j<=n;j++){
ch=getchar();
while(ch!='*'&&ch!='_') ch=getchar();
x[j][i]=(ch=='_');
if(x[j][i]&&((j>ex)||(j==ex&&i>ey))) ex=j,ey=i;
}
}
}
dp();
printf("%lld",re);
}