关灯
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
有一个 的方阵,每个位置上都有一盏灯,这些灯有亮有暗。每次,可以选择一个格子,选定后它与它相邻的格子的亮暗状态都会发生改变,在此处,相邻指的是 4-相邻 (有公共边),如下图:
易知,如果某一个格子被选择了偶 (奇) 数次,效果等价于它没有被选择 (被选择),因此,我们限制每个格子至多被选择 次。
给定初始方阵中每盏灯的亮暗情况,请输出一个使所有灯都熄灭的方案,格式见输出格式。
如果有多个方案,输出任意一个方案,如果无解,输出 No solution
。
Format
Input
第一行包含一个正整数 ,表示方阵的行数和列数。
接下来的 行,每行包含一个长度为 的字符串,其中第 行的第 个字符为 #
,如果原来灯阵中第 行第 列的灯是亮的,否则为 .
。
Output
如果有解,则输出 行,每行一个长度为 的字符串,其中第 行的第 个字符为 #
,如果需要选择灯阵中第 行第 列的格子,否则为 .
;
如果无解,输出一行,为 No solution
。
Samples
4
####
#..#
#..#
####
#..#
....
....
#..#
5
#....
.....
.....
.....
.....
No solution
5
.###.
.##.#
#...#
##..#
#####
...#.
.#..#
#....
.....
.#..#
Limitation
对于所有数据,满足 。
Subtask # | 分值 | 其它性质 | |
---|---|---|---|
1 | 无 | ||
2 | |||
3 | 保证初始所有的灯都是亮的 | ||
4 | 无 | ||
5 | 保证有且仅有一解 (旋转、翻转被认为是不同的解) | ||
6 | 无 |
暑期模拟赛 一
- Status
- Done
- Rule
- IOI
- Problem
- 5
- Start at
- 2024-7-11 8:30
- End at
- 2024-7-11 12:00
- Duration
- 3.5 hour(s)
- Host
- Partic.
- 9