rockdu
题目描述
曾经有一款流行的游戏，叫做 Infinity Loop，先来简单的介绍一下这个游戏:
游戏在一个 n×m 的网格状棋盘上进行，其中有些小方格中会有水管，水管可能在方格某些方向的边界的中点有接口，所有水管的粗细都相同，所以如果两个相邻方格的公共边界的中点都有接头，那么可以看作这两个接头互相连接。水管有以下 15 种形状：
游戏开始时，棋盘中水管可能存在漏水的地方。
形式化地:如果存在某个接头，没有和其它接头相连接，那么它就是一个漏水的地方。
玩家可以进行一种操作：选定一个含有非直线型水管的方格，将其中的水管绕方格中心顺时针或逆时针旋转 909090 度。
直线型水管是指左图里中间一行的两种水管。
现给出一个初始局面，请问最少进行多少次操作可以使棋盘上不存在漏水的地方。
输入格式
第一行两个正整数 n,m，代表网格的大小。
接下来 n 行每行 m 个数，每个数是 [0,15] 中的一个，你可以将其看作一个 4位的二进制数，从低到高每一位分别代表初始局面中这个格子上、右、下、左方向上是否有 水管接头。
特别地，如果这个数是 0，则意味着这个位置没有水管。
比如 3(0011(2)) 代表上和右有接头，也就是一个 L 型，而 12(1100(2)) 代表下和左有接头，也就是将 L 型旋转 180 度。
输出格式
输出共一行，表示最少操作次数。如果无法达成目标，输出 -1.
样例
样例输入 1
2 3 3 14 12 3 11 12
样例输出 1
2
样例输入 2
3 2 1 8 5 10 2 4
样例输出 2
-1
样例输入 3
3 3 9 11 3 13 15 7 12 14 6
样例输出 3
16
前传：*集训下午*
K404机房里……A14座位：巨佬*1，A12座位：dalao*1，A13：蒟蒻的我。
题目布置下来了……看看T1，嗯？无限之环？目测一下搜索过10，轮廓线40分。不过这100分怎么拿呀QAQ……此时A14、A12大佬已经打起了T1。*窥屏大法*，A14大佬写了一个……额，费用流？？愣了10分钟后，意识到这真是个费用流，不过这个连边简直……hhhhh。没办法，那就写16种连边吧QAQ……
--3个小时过去了，边还是没连完--
临走前问了问A12大佬连边怎么连的
大佬说：我用的轮廓线，因为有一维不会超long long，可以用map记录有效状态，比费用流快10倍……。
我：……mmp。
于是今天终于把这个坑填了！算是map优化轮廓线dp？代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#define LL long long
#define ItMap map<LL, int>::iterator
using namespace std;
const int maxn = 2e3 + 5, inf = 0x3f3f3f3f;
int mp[maxn][maxn], temUL = 9;
int n, m, nans;
LL nowst, stmax, hbit, nblk, lgst, now, k;
map<LL, int> dp[2];
inline int Lrot(int st) {return (st & 1) ? (st >> 1) + 8 : st >> 1;}
inline void Symmetry(int & st) {st = ((st & 2) << 1) | ((st & 4) >> 1) | ((st & 1) << 3) | ((st & 8) >> 3);}
int main() {
scanf("%d%d", &n, &m);
if(n <= m) {
for(register int i = 1; i <= n; ++i)
for(register int j = 1; j <= m; ++j)
scanf("%d", &mp[i][j]);
} else {
for(register int i = 1; i <= n; ++i)
for(register int j = 1; j <= m; ++j)
scanf("%d", &mp[j][i]), Symmetry(mp[j][i]);
swap(n, m);
}
stmax = (1ll << n + 1), hbit = 1ll << n;
dp[0][0] = 0;
for(register int j = 1; j <= m; ++j)
for(register int i = 1; i <= n; ++i) {
now ^= 1;
dp[now].clear();
for(register ItMap it = dp[now ^ 1].begin(); it != dp[now ^ 1].end(); ++it) {
if(it -> second == inf) continue;
k = it -> first;
nblk = mp[i][j], nans = dp[now ^ 1][k];
lgst = (k & 1) + ((k & hbit) != 0) * 8;
if(!(lgst ^ (nblk & temUL))) {
nowst = (k << 1) % stmax;
(nowst >>= 2) <<= 2, nowst |= (nblk & 2) | ((nblk & 4) >> 2);
//printf("STAY %d -> %d ", k, nowst);
if(!dp[now].count(nowst)) dp[now][nowst] = nans;
else dp[now][nowst] = min(dp[now][nowst], nans);
}
if(nblk == 5 || nblk == 10) continue;
nblk = Lrot(nblk);
if(!(lgst ^ (nblk & temUL))) {
nowst = (k << 1) % stmax;
(nowst >>= 2) <<= 2, nowst |= (nblk & 2) | ((nblk & 4) >> 2);
//printf("LT %d -> %d ", k, nowst);
if(!dp[now].count(nowst)) dp[now][nowst] = nans + 1;
else dp[now][nowst] = min(dp[now][nowst], nans + 1);
}
nblk = Lrot(nblk);
if(!(lgst ^ (nblk & temUL))) {
nowst = (k << 1) % stmax;
(nowst >>= 2) <<= 2, nowst |= (nblk & 2) | ((nblk & 4) >> 2);
//printf("OPP %d -> %d ", k, nowst);
if(!dp[now].count(nowst)) dp[now][nowst] = nans + 2;
else dp[now][nowst] = min(dp[now][nowst], nans + 2);
}
nblk = Lrot(nblk);
if(!(lgst ^ (nblk & temUL))) {
nowst = (k << 1) % stmax;
(nowst >>= 2) <<= 2, nowst |= (nblk & 2) | ((nblk & 4) >> 2);
//printf("RT %d -> %d ", k, nowst);
if(!dp[now].count(nowst)) dp[now][nowst] = nans + 1;
else dp[now][nowst] = min(dp[now][nowst], nans + 1);
}
}
if(i == n) {
for(ItMap k = dp[now].begin(); k != dp[now].end(); ++k)
if(k -> first & 1) k -> second = inf;
}
//printf("\n");
}
if(dp[now].count(0)) printf("%d", dp[now][0] != inf ? dp[now][0] : -1);
else printf("-1");
return 0;
}
没有帐号? 立即注册