1580 铺管道
题目来源： CodeForces 基准时间限制：1.5 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
收藏
关注
现在要在一个城市中铺设管道。
这个城市是由 n×m 小方格组成的。每一个小方格要么是空的（管道可以铺设在上面），要么是实的（管道不能铺在上面）。空的用’.’表示，实的用’#’表示。
管道铺设的规则如下：
· 整条管道是形状是宽度为1的折线；
· 管道只能铺设在空的格子上面；
· 管道的两个端点只能在边缘上，但是不能在角上；
· 管道最多只能转两个弯（90度）；
· 在管道上的格子有且只能有两个是在边缘上的；
· 如果管道是一条直线，那么他的两个端点必须是落在不同的边上；
· 对于管道上的非边缘格子，每一个格子会有且仅有两个相邻的其它格子在管道上；
· 对于管道上处于边缘的格子，仅有一个相邻的格子处于管道上。
下面有一些合法的管道铺设例子：
1 2 3 4 5 ....# ....# . * ..# ***** **** . . *** . ..# .. ..# * . ..# * . # ...# # .. *# # .. *# ..... ... * . ... * .
下面是一些非法铺设的例子：
1 2 3 4 5 . ** .# * ...# . * . *# ..... **** . . * . * . ..# .. ..# * . . *# * . # ...# # .. *# # * . *# ..... ... * . . *** .
这些例子中管道用’*’表示。
现在给定城市的地图，请计算一下有多少种方法铺设管道。
样例解释：
在这个样例中，有三种方法铺设管道（管道用'*'表示）。
1
2
3
.
*
.
.
*
.
...
.
*#
**#
**#
.
*
.
...
.
*
.
Input
单组测试数据。
第一行有两个整数 n,m (2≤n,m≤2000)，表示城市地图的高和宽。
接下来n行，每一行有m个字母，表示城市地图。
如果字符是’.’，表示该格子是空的，管道可以铺设。
如果字符是’#’，表示该格子是实的，管道不能铺设。 Output
输出一个整数，表示管道铺设方案的种数。 Input示例
样例输入1
3 3
...
..#
... Output示例
样例输出1
3 System Message (题目提供者) Visual C++的运行时限为：1500 ms ，空间限制为：131072 KB 示例及语言说明请按这里
允许其他 AC 的用户查看此代码，分享代码才能查看别人的代码并有机会获得勋章
题意很繁琐，问题就是求满足题目描述的管道数量。一开始想的广搜，果断超时。。但是好像cf不会超时啊。
后来查了发正解，发现问题可以转化为折线问题。我们可以把管道看做折线（其实没啥区别）
然后满足题意的折线无非4种。。借鉴一个大佬的图。。
图片来源：http://www.cnblogs.com/dancer16/p/7351701.html
然后我们就可以按照题目要求查找满足要求的直线了，为哦了避免重复计算，所以考虑先计算纵向的
然后折叠矩阵，交换位置（可能说的不是很对，词穷了），中间的细节很多，敲了半天一直wa。
然后借鉴了一位大佬的代码：http://blog.csdn.net/f_zyj/article/details/72909671，才避免了许多重复计算。很巧妙
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
#define inf 1000000000
#define mod 1000000007
#define maxn 2005
#define PI 3.1415926
#define lowbit(x) (x&-x)
#define eps 1e-9
char s[maxn];
bool a[maxn][maxn], b[maxn][maxn], c[maxn][maxn], d[maxn][maxn];
ll ans;
void solve(int n, int m, int flag)
{
int i, j, tmp;
memset(c, 0, sizeof(c));
memset(d, 0, sizeof(d));
for (i = 1;i <= n;i++)
for (j = 1;j <= m;j++)
c[i][j] = c[i - 1][j] | a[i][j];
for (i = n;i > 0;i--)
for (j = 1;j <= m;j++)
d[i][j] = d[i + 1][j] | a[i][j];
for (i = 2;i < n;i++)
{
tmp = 0;
c[i][1] = d[i][1] = 1;//防止把第一列给算进去。
if (!a[i][1] && flag)//为避免重复，只需算一次下...左...
tmp = 1;
for (j = 2;j < m;j++)
{
if (a[i][j])
{
tmp = 0;
continue;
}
ans += ((!c[i][j]) + (!d[i][j]))*tmp;
ans += ((!c[i][j] && !d[i][j - 1]) + (!c[i][j - 1] && !d[i][j]));
tmp += (!c[i][j - 1]) + (!d[i][j - 1]);//之后累加能组成下...右...上和上...右...下等折线
}
if (!a[i][m] && flag)//加上从前边任何一列开始为下...右...和上...右...的折线
ans += tmp + (!c[i][m - 1]) + (!d[i][m - 1]);//以及左右直达的直线
}
if (flag)//在算其他类型折线的同事横向直线顺带求出了，故直线只用再求一次
{
for (i = 2;i < m;i++)
ans += (!c[n][i]);
}
}
int main(void)
{
int n, m, i, j;
scanf("%d%d", &n, &m);
for (i = 1;i <= n;i++)
{
scanf("%s", s + 1);
for (j = 1;j <= m;j++)
a[i][j] = s[j] == '#';
}
solve(n, m, 1);
for (i = 1;i <= n;i++)
for (j = 1;j <= m;j++)
b[j][i] = a[i][j];
memset(a, 0, sizeof(a));
for (i = 1;i <= m;i++)
for (j = 1;j <= n;j++)
a[i][j] = b[i][j];
solve(m, n, 0);
printf("%lld\n", ans);
return 0;
}