#P18306. King's Festival
King's Festival
King's Festival
矮人国王希望用尽可能少的魔法灯照亮节日大厅。
大厅由 个方格组成。灯只能放在从左上角到右下角的主对角线上,每个主对角线方格至多放一盏灯。
一盏灯能够照亮:
- 它所在的方格;
- 与它在同一行的所有方格;
- 与它在同一列的所有方格;
- 与它在同一条对角线上的所有方格,两个对角线方向都包括在内。
有些灯已经固定在主对角线上,不能移动或移除。
求照亮大厅所有方格所需的最少灯数,并给出一种最优放置方案。灯数包括原来已经固定的灯。
输入格式
输入只有一行,包含一个长度为 的字符串,字符只可能为 . 或 #。
第 个字符为 #,表示主对角线从左上角起的第 个方格已经有一盏固定的灯;. 表示该位置还没有灯。
。
只有一组数据,没有测试组数 ,也没有单独输入的 ; 由字符串长度确定。
输出格式
第一行输出一个整数,表示最优方案中的总灯数,包括已经固定的灯。
第二行输出一个长度为 的 .、# 字符串,描述最终的放置方案,格式与输入相同。输入中的每个 # 在输出中仍必须是 #。
所有方格都必须被照亮。如果有多种最优方案,可以输出任意一种。
样例 1
......
4
###.#.
样例 2
.#.#...
4
.###.#.