#PQJ3164x16604. QOJ 3164_16604

    ID: 2911 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2024 集训字符串

QOJ 3164_16604

小 H 的棋盘 时间限制:1s 空间限制:1GB 题目描述 小 H 想要装饰他的棋盘。小 H 的棋盘有 个格子,构成一个 的网格,行从上到下标号 至 ,列从左到右标号 至 。这些格子四周线段的交点被称为格点,格点有 个。 下图是一个 棋盘的示意图,其中黑点为格点,格子中心标注了该格子的坐标. 小 H 的棋盘比较特殊:除了上下左右连接格点的线段,每个格子上额外有恰好一条对角线连接两个格 点,这条对角线有两种可能的选择: 左上至右下:称为 N 型。 右上至左下:称为 Z 型。 我们可以通过如下方式得到一个由 N 和 Z 构成的长度为 的字符串,表示每个格子的类型: 把每行的类型从左到右连接得到一个字符串,再把所有字符串按行从上至下的顺序连接起来。 定义这个字符串为这个棋盘的特征串。 由于想装饰他的棋盘,小 H 想给每个格点染成三种颜色之一。小 H 认为一个染色方案是优美的当且仅当 任意有线段相连的格点颜色不同。 下图展示了一个优美的染色方案,对应的特征串为 NNNZZZ 。 小 H 已经确定了某些格子的类型,并由此写下了对应的字符串 ,由 N 、Z 和 ? 三种字符构成,其中 ? 代表未确定。 请确定所有未确定的格子,使得至少一种优美的染色方案存在。请给出特征串字典序最小的解,或者报 告无解。 输入格式 第一行两个整数 。 第二行一个长度为 的字符串 ,仅可能包含 N 、Z 和 ? 三种字符。 输出格式 若有解,输出一行一个字符串,表示所求的字典序最小的特征串。 若无解,输出 -1 。 样例输入输出 样例输入 #1 2 3 ???ZZZ 样例输出 #1 NNNZZZ 样例输入 #2 2 2 NZZZ 样例输出 #2 -1 数据范围与约定 对于全部数据, 。 子任务 1( 分): 中不含 ? 。 子任务 2( 分): 。 子任务 3( 分): 。 子任务 4( 分):无特殊限制。