NKOJ 3253 (CQOI 2015) 标识设计（状压DP）

发表于 |
字数统计: 1,660字 | 阅读时长 ≈ 7min

3253【CQOI2015】标识设计

问题描述

一家名字缩写为LLL的公司正在设计logo，他们的初步方案是在一张方格上放置3个L形的图案以及一些额外的装饰性图形。例如：

NKOJ3253-1（灰色区域表示装饰性图形）

3个L图案和装饰性图形均放置在方格之中，且必须占满方格。"L"的横竖笔画长短均可，但长度必须大于0（即不能退化为一条线段）。另外，为了使L图案醒目且容易辨别，设计师规定3个L形图案之间不能有重叠或交叉的部分。当然，L形图案也不能穿过装饰图形或与之重叠。
 现在设计师已经确定了所有装饰性图形的位置，希望你计算一下放置不同的L形图案总共可以设计出多少个logo。

输入格式

输入文件第一行包含两个空格分开的正整数n和m，分别表示方格的行数和列数。
接下来n行，每行m个字符，为"."或"#"。"#"表示该方格为装饰性图形，"."表示可以放置L图案的空白区域。

输出格式

输出一个整数，为可能的logo总数。

样例输入

4 4
....
#...
....
..#.

样例输出
样例输出

4

提示

样例解释：

NKOJ3253-2

    满足要求的logo只有这4种。注意，颜色只是为了便于说明，不影响方案数，因为在实际的logo中3个L图案将使用相同的色彩、纹理和光泽。

数据范围：
    对于30%的数据，n,m≤5。
    对于100%的数据，2≤n,m≤30。

首先，根据题意很容易想到利用DP来求解，那么问题在于如何确定状态。
我们可以将这三个“L”型的标记看成三条路径，然后问题就变成求三条互不相交的“L”型的路径。
观察“L”的特点我们发现，相当于是我在拓展这条路的时候只能向下或向右走，于是我们可以列出如下状态：
$F[x][y][re][s][ty]$
我们来解释一下这个状态，他表示的是我当前讨论到了(x,y)这个格子，还剩下re个“L”没有放，然后s是一个状压的结果，他表示在二进制下，当前在某些列存在向下走的路径，但还没有开始向右走，ty表示当前是否有路径正在向右走。

由于可能的转移只能是路径向下或向右延伸，因此我们可以推出转移方式（以下可以直接看代码）：
若当前格子在一条向下走的路径上，那么他有向下和向右两种转移。
若当前格子在一条向右走的路径上，那么他有向右和停止两种转移。
若当前格子不在路径上，并且res>0&&y≠m，那么他可以作为一条路径的起点。
若当前格子是障碍格，并且处在一条路径上，那么返回0。
若当前格子同时在一条向右走的路径和向下走的路径上，那么返回0。
若当前y>m，跳到下一行。
若当前x>n，但还有“L”没放或者还有路径在向下走，那么返回0，否则返回1。

从上到下，从左到右，逐行逐列DP即可。

最后我们来看看s表示的状态，由于我们最多只需要放3个“L”，那么我们最多同时存在三列有向下走的路径，因此s的状态总数的最大值等于4525种，貌似还没有这么多，忽略。因此我们可以提前离散化。

于是我们可以用记忆化搜索的形式来写，具体情况参见代码。

代码写的很渣，亟待改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#define N 32
#define M 5000
#define ll long long
using namespace std;
ll n,m,F[N][N][4][M][2];
char G[N][N];
map<ll,ll>Q;
ll R[M],cnt;
ll DP(ll x,ll y,ll re,ll s,ll ty)//讨论到(x,y)，还剩下 res个L没放，当前状态是s，表示向下的路径的位置，ty表示是否处在向右的路径上 
{
	ll i,j,k,tmp=0,t=R[s];//离散化回来 
	if(F[x][y][re][s][ty]>-1)return F[x][y][re][s][ty];//记忆化搜索 
	if(x>n)
	{
		if((!re)&&(!t))return F[x][y][re][s][ty]=1;//L已经放完并且都已经完成了向右走，返回1 
		return F[x][y][re][s][ty]=0;//否则返回0 
	}
	if(y>m)
	{
		if(ty)return F[x][y][re][s][ty]=0;//如果当前处在向右的路径上，返回0 
		return F[x][y][re][s][ty]=DP(x+1,1,re,s,0);//否则跳到下一行继续dp 
	}
	if((1<<y-1)&t)//如果当前格子在一条向下的路径上 
	{
		if(G[x][y]=='#'||ty)return F[x][y][re][s][ty]=0;//如果他同时在一条向右的路径上，或者是障碍，返回0 
		return F[x][y][re][s][ty]=DP(x,y+1,re,s,0)+DP(x,y+1,re,Q[t^(1<<y-1)],1);//否则返回这条路径向右走和向下走的方案和（如果开始向右走，那么不能再向下走，记变状态） 
	}
	if(ty)//如果当前格子在一条向右的路径上 
	{
		if(G[x][y]=='#')return F[x][y][re][s][ty]=0;//如果当前格子是障碍，返回0 
		return F[x][y][re][s][ty]=DP(x,y+1,re,s,1)+DP(x,y+1,re,s,0);//否则返回这条路径终止和向右走的方案和 
	}
	tmp=DP(x,y+1,re,s,ty);//什么也不做，讨论下一格 
	if(re>0&&G[x][y]=='.'&&y<m)tmp+=DP(x,y+1,re-1,Q[t|(1<<y-1)],ty);//如果当前格子可以作为一条路径的起点，那么新增一条路径 
	return F[x][y][re][s][ty]=tmp;//返回当前的方案数 
}
int main()
{
	memset(F,-1,sizeof(F));
	ll i,j,k,t,tt,ttt;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++)scanf("%s",&G[i][1]);
	
	Q[0]=++cnt;R[cnt]=0;//离散化状态 
	for(i=1;i<=m;i++)
	{
		t=1<<i-1;
		Q[t]=++cnt;R[cnt]=t;
		for(j=i+1;j<=m;j++)
	    {
		    tt=t|(1<<j-1);
		    Q[tt]=++cnt;R[cnt]=tt;
		    for(k=j+1;k<=m;k++)
		    {
		    	ttt=tt|(1<<k-1);
		    	Q[ttt]=++cnt;
		    	R[cnt]=ttt;
		    }
	    }
	}
	
	ll ans=DP(1,1,3,0,0);
	cout<<ans;
}