$$沙耶的玩偶(doll)$$

题目链接：$jzoj3457$

题目

在美鱼和理树后援团拯救世界的同时，外表柔弱的理树也开始坚强起来，思考着离开这个世界的办法。误打误撞地，她遇上了正在教室破坏课桌打开迷宫入口的沙耶。沙耶告诉理树，这个世界的出口就是这个迷宫的出口。于是理树毫不犹豫地跟沙耶一起跳进了迷宫。在迷宫里，两个女孩子互帮互助，一会儿割绳子，一会儿泡温泉，一会儿雕冰块，跌跌撞撞地走到了终点。不出所料，终点也有一个机关在等着她们。

终点的机关是一个立着的 $m\ast n$ 的方格棋盘，在有些格子上放了一个玩偶，而有些地方直接挖了个大坑。只有取走所有玩偶才能打开出口。但是，由于奇怪的设定，理树和沙耶不能直接触碰玩偶，他们需要操纵机器人来收集它。机器人的走法很奇怪，和国际象棋的马有点像，只不过马可以走任意方向的 $1\ast 2$ 路线，它们只会由上往下走$r\ast c($或$c\ast r)$的路线，不能回头。而机器人一旦经过一个有玩偶的格子，那个格子上的玩偶将被回收，并且在机器人离开时，那个格子会变成一个坑。理树可以把机器人放在任何一个有玩偶的格子上作为起点，也可以在任何一个有玩偶的格子回收机器人。机器人行走可以视为瞬移，只不过每一次设置新起点都会消耗 $1$ 时间。并且，有坑的格子不能落脚。

就在这个紧要关头，玩偶狂热爱好者的沙耶却流着口水智商归$0$。理树不得不转而求助你，帮忙计算出最少多少时间就能收集到所有玩偶。

输入

第一行包含 $4$ 个整数$M$、$N$、$R$、$C$，意义见问题描述。接下来 $M$ 行每行一个长度为 $N$ 的字符串。如果某个字符是${}^{\prime }{.}^{\prime }$，表示这个地方有一个玩偶；如果这个字符是${}^{\prime }{x}^{\prime }$，表示这个地方是坑。

输出

输出一个整数，表示最短时间。

样例输入

3 3 1 2 ... .x. ...

样例输出

4

样例解释

数据范围

$30\%$的数据中，$1<=M,N<=4$，$1<=R,C<=3$。

$70\%$的数据中，$1<=M<=20$，$1<=N<=4$，$1<=R,C<=3$。

$100\%$的数据中，$1<=M,N<=50$，$1<=R,C<=10$。

思路

这道题是一道二分图。

由题目可以得到，如果现在机器人在$(x,y)$，那它最多只能走四个位置： $$(X+R,Y+C),(X+R,Y-C),(X+C,Y+R),(X+C,Y-R)$$ 我们要让机器人捡完所有的玩具，其实就是要让机器人走完所有可以走的点。 而且这个图是一个有向无环图。

那我们其实可以用二分图来解决。 左边右边都建$m\ast n$个点，如果由编号为$i$的点可以连接到编号为$j$的点，就在左边的$i$向右边的$j$连一条边。

然后我们就最大匹配二分图，最终答案就是玩偶数量$-$最大匹配数。

代码

#include<cstdio> using namespace std; struct node { int to, next; }e[100001]; int m, n, r, c, a[51][51], kk, le[6001], kkk, ans, fa[6001]; bool in[6001]; char C; void add(int x, int y) { e[++kkk] = (node){y, le[x]}; le[x] = kkk; } bool work(int now) { for (int i = le[now]; i; i = e[i].next) if (in[e[i].to]) { in[e[i].to] = 0; if (!fa[e[i].to] || work(fa[e[i].to])) { fa[e[i].to] = now; return 1; } } return 0; } int main() { scanf("%d %d %d %d", &m, &n, &r, &c);//读入 for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { C = getchar();//读入 while (C != '.' && C != 'x') C = getchar(); if (C == '.') { a[i][j] = ++kk; if (i - r > 0 && j - c > 0 && a[i - r][j - c])//可以走的四个位置 add(kk, a[i - r][j - c] + m * n + 10); if (i - r > 0 && j + c <= n && a[i - r][j + c]) add(kk, a[i - r][j + c] + m * n + 10); if (i - c > 0 && j - r > 0 && a[i - c][j - r]) add(kk, a[i - c][j - r] + m * n + 10); if (i - c > 0 && j + r <= n && a[i - c][j + r]) add(kk, a[i - c][j + r] + m * n + 10); } } for (int i = 1; i <= kk; i++) { for (int j = 1; j <= kk; j++) in[m * n + 10 + j] = 1;//初始化 if (work(i)) ans++;//从每一个点作为开始点 } printf("%d", kk - ans);//输出 return 0; }