Light Up 拼图问题

描述

Light Up 是一个拼图，设置在一个矩形板上，分成较小的方块。棋盘上的一些方格是 “空的” （下图中的白色方格），一些方格是 “障碍” （下图中的深色方格）。障碍方格可能有一个与之关联的整数 $i$ （$0 \leq i \leq 4$）。

图 2：（a） 6 行、7 列和 7 个障碍的拼图;（b） 解开谜题。

在这个谜题中，目标是通过在其中一些方格中放置灯来“点亮”所有空方格（灯在图中被描绘成圆圈）。每盏灯都照亮它所在的方格，以及与其对齐的所有方格，水平或垂直方向，直到障碍物方格或板端。

获胜的配置满足以下条件：

1. 所有空方格必须点亮；
2. 任何灯都不能由另一盏灯点亮；
3. 所有编号的障碍方块必须恰好有该数量的灯相邻（在上面、下面和侧面的四个方块中）；
4. 没有编号的障碍方块可以有任意数量的灯相邻。

您必须编写一个程序来确定达到 Winning 配置所需的最小灯数。

输入

输入包含多个测试用例。测试用例的第一行包含两个整数 $N$、$M$，分别表示板的行数和列数（$1 \leq N \leq 7$， $1 \leq M \leq 7$）。第二行包含一个整数 $B$，表示障碍方数 （$0 \leq B \leq N \times M$）。接下来的 $B$ 行中的每一行都描述了一个障碍，包含三个整数 $R$、$C$ 和 $K$，分别代表行号 （$1 \leq R \leq N$）、列号 （$1 \leq C \leq M$） 和障碍号 （$-1 \leq K \leq 4$）;$K = -1$ 表示障碍未编号。输入结束由 $N = M = 0$ 表示。

输出

对于输入中的每个测试用例，您的程序必须生成一行输出，其中包含一个整数，表示达到获胜配置所需的最小灯数（如果存在此类配置），或者包含“无解决方案”字样。

输入数据 1

2 2
0
2 2
1
2 2 1
6 7
7
2 3 -1
3 3 0
4 2 1
5 4 3
5 6 2
1 7 -1
6 5 -1
0 0

输出数据 1

2
No solution
8

源于

南美洲 2005