P5056 【模板】插头dp
2024-08-31 21:04:27
\(\color{#0066ff}{ 题目描述 }\)
给出n*m的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？
\(\color{#0066ff}{输入格式}\)
第1行，n,m(2<=n,m<=12)
从第2行到第n+1行，每行一段字符串(m个字符)，"*"表不能铺线，"."表必须铺
\(\color{#0066ff}{输出格式}\)
输出一个整数，表示总方案数
\(\color{#0066ff}{输入样例}\)
4 4
**..
....
....
....
\(\color{#0066ff}{输出样例}\)
2
\(\color{#0066ff}{数据范围与提示}\)
none
\(\color{#0066ff}{ 题解 }\)
插头DP本来以为多niubility的算法原来本质还是个DP，就是情况多了点qwq
状压分割线，有三种情况，无，左插头，右插头（详见洛谷题解懒得写了）
只要明白状态分析出所有情况即可
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
std::unordered_map<LL, LL> f[2];
//我TM就不写hash表
int n, m, s, t;
bool mp[100][100];
char getch() {
char ch = getchar();
while(ch != '*' && ch != '.') ch = getchar();
return ch;
}
void init() {
n = in(), m = in();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
mp[i][j] = getch() == '.';
if(mp[i][j]) s = i, t = j;
}
}
LL pos(int v, int x) { return (v << (x << 1)); }
//返回第x大块的v状态（两个二进制来状压）
LL work() {
int now = 0, nxt = 1;
f[0][0] = 1;
LL U = (1LL << ((m + 1) << 1)) - 1;
//全集
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
f[nxt].clear();
for(auto &k:f[now]) {
LL S = k.first, val = k.second;
LL L = (S >> ((j - 1) << 1)) & 3, R = (S >> (j << 1)) & 3;
//分割线（L是当前竖着的那个，R是紧接着横着的那个）
if(!mp[i][j]) {
if(!L && !R) f[nxt][S] += val;
continue;
}
// 0 0
if(!L && !R) {
if(mp[i][j + 1] && mp[i + 1][j]) f[nxt][S ^ pos(1, j - 1) ^ pos(2, j)] += val;
//0 0 -> 1 2
}
//2 1
else if(L == 2 && R == 1) {
//2 1 -> 0 0
f[nxt][S ^ pos(L, j - 1) ^ pos(R, j)] += val;
}
// 0 1 // 1 0 // 0 2 // 2 0
else if(!L || !R) {
//0 1 // 0 2
if(!L) {
//拐弯
if(mp[i][j + 1]) f[nxt][S] += val;
//不拐弯
if(mp[i + 1][j]) f[nxt][S ^ pos(L, j - 1) ^ pos(L, j) ^ pos(R, j - 1) ^ pos(R, j)] += val;
}
//同上
else if(!R) {
if(mp[i][j + 1]) f[nxt][S ^ pos(L, j - 1) ^ pos(L, j) ^ pos(R, j - 1) ^ pos(R, j)] += val;
if(mp[i + 1][j]) f[nxt][S] += val;
}
}
//1 1 // 2 2
else if(L == R) {
// 1 1
if(L == 1) {
int du = 0;
//1 1 -> 0 0 但是源头接口处右插头变成左插头
for(int p = j; ; p++) {
LL o = (S >> (p << 1)) & 3;
if(o == 1) du++;
if(o == 2) du--;
if(!du) {
//原来状态消去，弄上新状态
f[nxt][S ^ pos(L, j - 1) ^ pos(R, j) ^ pos(2, p) ^ pos(1, p)] += val;
break;
}
}
}
//根上面差不多
else if(L == 2) {
int du = 0;
for(int p = j - 1; ; p--) {
LL o = (S >> (p << 1)) & 3;
if(o == 1) du--;
if(o == 2) du++;
if(!du) {
f[nxt][S ^ pos(L, j - 1) ^ pos(R, j) ^ pos(2, p) ^ pos(1, p)] += val;
break;
}
}
}
}
//本状态当且仅当是终点，用于封口
else if(L == 1 && R == 2 && i == s && j == t) return val;
}
std::swap(now, nxt);
}
f[nxt].clear();
//末尾的竖分割线到了下一行就变成了行首的分割线，把状态《《给分割线腾出地方
for(auto &k:f[now]) f[nxt][(k.first << 2) & U] += k.second;
std::swap(now, nxt);
}
return 0;
}
int main() {
init();
printf("%lld\n", work());
return 0;
}
最新文章
- 你可能不知道的陷阱, IEnumerable接口
- sshd安装
- checkinstall打包工具使用
- MyEclipse 8.5 优化实例
- ASP.NET中 WebForm 窗体控件使用及总结【转】
- MyEclipse中文乱码解决方法
- HDU 1405 第六周 J题
- java-基础练习题
- Linux parted 分区
- linux的终端，网络虚拟终端，伪终端(转)
- RocketMQ在windows上安装和开发使用
- .NET中删除空白字符串的10大方法
- oracle用户权限的问题
- java的设计模式 - 单例模式
- Python学习第十二篇——切片的使用
- U-boot2010.06移植--阶段一
- 【转】STM32 独立看门狗简介
- CSS颜色
- [UE4]函数参数引用
- 跟我学SharePoint 2013视频培训课程——理解SharePoint网站的体系结构（3）