P2407 [SDOI2009] 地图复原 题解

· · 题解

考虑每行第一个出现的 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，如果发现了更短的写法请告诉我