YCOJ227B 摆放鞋子

题意

给定一个由 \(['L', 'R']\) 组成的网格图。

每个点有一个方向，用 \(['U', 'D', 'L', 'R']\) 表示。

每次操作可以选择两个相邻的点，使其中一个顺时针旋转另一个逆时针旋转。

称一个匹配为站在两个相邻点所朝的方向上使得左边是 \(L\) 右边是 \(R\)。

Sol

考虑操作前后不变的东西，注意到如果我们将 \(['U', 'R', 'D', 'L']\) 分别设为 \([0, 1, 2, 3]\) 那么整张图的权值和 \(mod 4\) 不变。

考虑求得最大匹配，不难想到二分图最大匹配。

注意到操作实际上可以改成任意两个点操作。

那么，如果当前图并没有匹配完，还有剩余的节点，一定能找到一个点将不对的方向转过来。

所以只有完美匹配的情况才可能使得答案 \(-1\)。

考虑两种不同的完美匹配，发现假如一个行匹配变成一个列匹配，那么后面的列匹配会变成行匹配，因为是完美匹配，所以这一定构成一个封闭的多边形，而又因为是网格图，所以这个多边形是偶数个角，所有完美匹配的方案的权值是相同的。

所以，直接做完二分图匹配，随便输一种方案看是否权值相等即可。