自动搬运

查看原文

来自洛谷，原作者为

	ganpig bilibili @蔗蓝

搬运于2025-08-24 21:37:22，当前版本为作者最后更新于2023-11-07 16:15:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑每行第一个出现的 T，在水平方向上一定是向右连路的，因为假如是向左而左边没有 T 的话……那岂不是要一直连到地图之外？

既然是向右连，那就只能连到下一个 T 然后转成竖直方向的了。那如果有第三个 T，还是只能向右连，连到第四个……以此类推，依次配对。

竖直方向同理，每一列的第一个和第二个 T 配对，第三个和第四个 T 配对……全部连上就得到了答案。

但是！直接一小段一小段连过去，似乎写起来还是有点麻烦呢？为了偷懒，再多想一步：水平方向上的一小段需要连路，当且仅当它正左侧的 T 数量为奇数；竖直方向上的一小段需要连路，当且仅当它正上方的 T 数量为奇数。所以，把所有的 T 当成 1，维护每一行、每一列的异或和即可，用 bitset 很好实现。输出时还可以用 "..."[...] 这个语法糖来偷偷懒。

$\text{Code}$

#include <bits/stdc++.h>
int main() {
    int n, m;
    std::cin >> n >> m;
    std::bitset<1000> s, t;
    while (n--) {
        std::string str;
        std::cin >> str;
        for (int i = 0, a = 0; i < m; i++)
            printf("o%c", "\n -"[(i != m - 1) + (a ^= t[i] = str[i] == 'T')]);
        if (!n)
            break;
        s ^= t;
        for (int i = 0; i < m; i++)
            printf("%c%c", " |"[s[i]], " \n"[i == m - 1]);
    }
}

PS：这题的代码目前已经被压到了 146B，如果发现了更短的写法请告诉我