CF929B Места в самолёте

飞机上有 $n$ 排座位。从上方看，每排座位分布为：左侧有 $3$ 个座位，然后是过道，然后是中间 $4$ 个座位，再是另一个过道，最后是右侧 $3$ 个座位。 已知部分座位已被乘客占用。乘客分为两类：常旅客（即经常乘坐飞机的乘客）和普通乘客。 你的任务是安排剩余的 $k$ 名普通乘客，使得所有常旅客的邻居总数尽可能少。若两名乘客在同一排且中间没有其他座位或过道，则他们互为邻居。如果一名乘客同时是两名常旅客的邻居，则在总邻居数中应计两次。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 100$，$1 \leq k \leq 10 \cdot n$），分别表示飞机的排数和需要安排的普通乘客人数。 接下来 $n$ 行，每行描述一排座位。如果某个字符为 '-'，表示过道；为 '.'，表示空座；为 'S'，表示该座位已被常旅客占用；为 'P'，表示该座位已被普通乘客占用。 保证空座数量不少于 $k$。保证所有排的格式均符合题目描述。

第一行输出常旅客的邻居总数的最小值。 接下来输出一种使常旅客邻居总数最小的乘客安排方案，格式与输入相同。如果在空座上安排了一名普通乘客，则将该位置的 '.' 替换为小写字母 'x'。

由 ChatGPT 4.1 翻译