洛谷P5372 [SNOI2019]积木题解

题目链接：P5372 [SNOI2019]积木

题意：

有一块 \(n\) 行 \(m\) 列的网格板， \(n,m\) 都是奇数。网格上平铺着一些 \(1\times 2\) 的积木。积木可以旋转，不能重叠。这些积木共有 \(\frac{nm-1}{2}\) 块，也就是说，网格板上只有一格的空位。

你可以做两种操作：

将一块与空白格相邻（指有公共边）的积木旋转 \(90^\circ\) 到空白格中；

将一块与空白格积木相邻的积木平移至空白格中。

如图所示（被移动的积木颜色较浅）：

请你用以上两种操作将给定的网格板变换为指定的状态。

输入格式：

第一行两个正奇数 \(n,m\) ，分别表示网格的行数和列数。

接下来 \(n\) 行，每行 \(m\) 个字符，描述网格板的初始状态：

<表示这个格子是一块积木的左半部分；

>表示这个格子是一块积木的右半部分；

n表示这个格子是一块积木的上半部分；

u表示这个格子是一块积木的下半部分；

o表示这个格子是空的。

接下来另外 \(n\) 行，每行 \(m\) 个字符，描述你需要将网格板变成的目标状态，格式同上。

输出格式：

你需要输出一个字符串，按顺序表示你的操作：

L表示你移动了空白格左侧的积木；

R表示你移动了空白格右侧的积木；

U表示你移动了空白格上方的积木；

D表示你移动了空白格下方的积木。

当然，没有操作的话输出空串就好了。

数据范围：

你输出的操作序列长度不能超过 \(8\times 10^6\) 。

对于所有数据， \(1\leq n,m\leq 2000\) 。

考虑变换方块的操作，实际上是更改了两个节点的匹配。

而原图始终是二分图，因此考虑取两个匹配的对称差 \(M = M_1 \oplus M_2\) 。

此时 \(M\) 通常由若干环和一条链构成，链长度是否大于 \(1\) 取决于 \(M_1,M_2\) 的空格是否在同一位置，如图。

首先考虑只有一条链的情况，我们可以通过不断更改这条路径上的匹配消掉它。

接着考虑如何消掉环。注意到当空格在环的附近时，可以让环的边全部重新匹配，并且最终空格位置不变。

不过在具体实现时，我们不需要找到所有的环，可以在消完链之后暴力 dfs 残留的边，这些边一定位于环上。

由于每个点至多被搜到一次，因此时间复杂度为 \(\mathcal{O}(nm)\) ，操作次数不超过 \(2nm\) （至多访问 \(2\) 次）

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3 + 15))
#define N2 (N * N)
const char out[4] = {'L', 'U', 'R', 'D'};

char used[N2],str[N],obuf[N2 * 2];
int n,m,O,B1,B2,M1[N2],M2[N2];
int d[4],buf[N * 2],*rd = buf + N;
int readMap(int *match)
{
    int t = 1, blank = 0;
    for(int i = 0,j; i < n; i++)
        for(cin >> str,j = 0; j < m; j++, ++t)
            switch(str[j])
            {
                case 'o': blank = t; break;
                case '<': match[t] = t + 1; break;
                case '>': match[t] = t - 1; break;
                case 'n': match[t] = t + m; break;
                case 'u': match[t] = t - m; break;
            }
    return assert(blank),blank;
}
void move(int dir)
{
    int x = M1[B1] = B1 + d[dir];
    swap(B1, M1[x]); M1[B1] = 0; obuf[O++] = out[dir];
}
void solve() { for(; B1 != B2; move(rd[M2[B1] - B1])); }
void output(int dir) { int B = B1; for(move(dir); B1 != B; move(rd[M2[B1] - B1])); }
void dfs()
{
    int x = B1, i,j,y; bool ban = used[x] = true;
    for(i = 0; i < 4; i++)
    {
        switch(i)
        {
            case 0: ban = !((x - 1) % m); break;
            case 1: ban = (x <= m); break;
            case 2: ban = !(x % m); break;
            case 3: ban = x >= (n - 1) * m; break;
        }
        if(ban || used[y = x + d[i]]) continue;
        if(M1[y] != M2[y]) output(i);
        used[y] = true; j = rd[y - M1[y]];
        move(i); dfs(); move(j); assert(x == B1);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    rd[d[0] = -1] = 0; rd[d[1] = -m] = 1;
    rd[d[2] = 1] = 2; rd[d[3] = m] = 3;
    B1 = readMap(M1); B2 = readMap(M2);
    solve(); dfs(); cout << obuf << '\n';
    return 0;
}