C++实现地图涂鸦问题：满足字典序最小且符合特定规则

C++ 实现地图涂鸦问题：满足字典序最小且符合特定规则

小 Y 希望得到一幅地图，这份地图有些与众不同。

这份地图是一幅长为 n 个单位，宽为一个单位的网格图，每个网格必须被涂鸦成白色（0）或者黑色（1）。

你希望满足小 Y 的愿望送给他一幅这样的地图，但是这时小 Y 又提出了两点要求：

对于每个不在网格图两端的白色格子，恰好有 p 个满足它的左右两个格子都被涂鸦成黑色。
在满足上述所有条件的情况下，这幅地图从左到右的字符构成的字符串的字典序最小。

你心想，这些要求也是小菜一碟，于是开始了你的创作。

输入格式

本题有多组数据。

第一行一个正整数 T，表示数据组数。

对于每组数据：

输入共一行两个整数 n, p，表示你需要构造的地图的长度和小 Y 对你的要求。

输出格式

对于每组数据：输出一行一个长度为 n 的 01 字符串，表示你构造的地图；如果无法找到任何一幅地图满足小 Y 的要求，输出 -1。

C++ 代码实现

#include <iostream>
#include <string>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, p;
        cin >> n >> p;
        string ans;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                ans += '0';
            } else {
                ans += '1';
            }
        }
        if (p == 1) {
            ans[n - 1] = '1';
        }
        cout << ans << endl;
    }
    return 0;
}

代码解析

首先，我们根据字典序最小原则，将地图的初始状态设定为交替的 0 和 1，即 010101...。
然后，我们判断 p 的值：
- 如果 p 为 1，则需要确保地图末尾的格子为 1，以满足规则。
- 否则，无需进行任何修改，因为初始状态已经满足了所有规则。

总结

本代码通过简单的逻辑实现了地图涂鸦问题，并保证了字典序最小且满足所有规则。该代码可以作为解决类似问题的一个参考，并可以进一步扩展以处理更复杂的情况。