Light Up 拼图问题的解题方法分析

问题背景

Light Up 是一个经典的组合优化问题，目标是在一个 $N \times M$ 的网格中放置尽可能少的灯，满足以下条件：

1. 点亮所有空方格：每盏灯可以照亮其所在行和列，直到遇到障碍物或边界。
2. 避免灯之间的直接照射：任何灯不能被其他灯直接照亮。
3. 满足编号障碍的要求：编号障碍 $K$ 的周围必须恰好有 $K$ 盏灯。
4. 未编号障碍的灵活性：未编号障碍可以有任意数量的灯。

解题方法

数据结构与初始化

1. 地图表示：

   • 使用二维数组 map[N][M] 表示棋盘状态：
     • -4 表示空方格；
     • -1 表示未编号障碍；
     • $[0, 4]$ 表示编号障碍；
     • -3 表示障碍无法被照亮；
     • -2 表示放置了灯。
   • 初始化时，将所有方格设为 -4，障碍按输入填充。

2. 障碍存储：

   • 定义结构体 node 存储障碍的位置和编号。
   • 使用向量 b 存储所有编号障碍。

3. 方向数组：

   • 定义方向数组 dx 和 dy，用于遍历上下左右四个方向。

关键函数

1. 判断是否可以放置灯

函数 can(x, y) 判断 $(x, y)$ 是否可以放置灯：

• 空方格是否未被照亮；
• 是否满足灯之间不直接照射的条件；
• 是否在障碍附近没有冲突。

2. 模拟放置灯的效果

函数 creat(x, y) 模拟放置灯的效果：

• 将灯放置位置标记为 -2；
• 将灯能照亮的区域标记为 -3。

3. 检查当前状态是否合法

函数 isok() 检查当前放置的灯是否满足所有条件：

• 所有空方格是否已被点亮；
• 编号障碍周围的灯数量是否匹配。

4. 深度优先搜索（DFS）

函数 dfs(v, tot) 使用 DFS 遍历所有可能的灯放置方案：

• 参数 v 表示当前考虑的方格索引；
• 参数 tot 表示当前放置的灯总数；
• 如果当前状态合法且灯数更少，则更新答案。

主程序逻辑

1. 读取输入：

   • 循环读取测试用例，直到 $N = M = 0$ 结束。

2. 初始化与处理障碍：

   • 初始化棋盘和障碍向量；
   • 根据输入填充障碍信息。

3. DFS 搜索：

   • 调用 dfs(0, 0) 开始搜索；
   • 如果找到可行解，输出最少灯数；否则输出 "No solution"。

代码实现

以下是基于上述方法的代码实现：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define inf 0x3f3f3f3f
#define min(x, y) ((x) < (y) ? (x) : (y))

// 定义方向数组
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

// 地图大小
int map[10][10];
int tmap[10][10];
int vis[10][10];

// 当前棋盘大小
int n, m, ans;

// 障碍结构体
struct node {
    int x, y, num;
};

// 存储所有障碍
vector<node> b;

// 判断坐标是否在棋盘内
bool inmap(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// 判断是否可以放置灯
bool can(int r, int c) {
    if (map[r][c] != -4) return false; // 不是空方格
    for (int d = 0; d < 4; d++) {
        int x = r, y = c;
        while (inmap(x + dx[d], y + dy[d])) {
            x += dx[d];
            y += dy[d];
            if (vis[x][y]) return false; // 被其他灯照亮
            if (map[x][y] >= -1) break; // 遇到障碍或边界
        }
    }
    // 检查右上方是否有冲突
    int nx = r + dx[3], ny = c + dy[3];
    if (inmap(nx, ny) && map[nx][ny] >= -1 && nx >= 1) {
        while (inmap(nx + dx[0], ny + dy[0])) {
            if (vis[nx += dx[0]][ny += dy[0]]) {
                return true;
            }
        }
    }
    return true;
}

// 模拟放置灯的效果
void creat(int x, int y) {
    tmap[x][y] = -2; // 放置灯
    for (int i = x - 1; i >= 0; i--) {
        if (map[i][y] >= -1) break;
        tmap[i][y] = -3; // 标记照亮区域
    }
    for (int i = x + 1; i < n; i++) {
        if (map[i][y] >= -1) break;
        tmap[i][y] = -3;
    }
    for (int i = y - 1; i >= 0; i--) {
        if (map[x][i] >= -1) break;
        tmap[x][i] = -3;
    }
    for (int i = y + 1; i < m; i++) {
        if (map[x][i] >= -1) break;
        tmap[x][i] = -3;
    }
}

// 检查当前状态是否合法
bool isok() {
    memcpy(tmap, map, sizeof(map)); // 复制地图状态
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[i][j]) creat(i, j); // 模拟放置灯
        }
    }
    // 检查是否有未照亮的空方格
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tmap[i][j] == -4) return false;
        }
    }
    // 检查编号障碍的灯数量
    for (int i = 0; i < b.size(); i++) {
        int tot = 0;
        for (int d = 0; d < 4; d++) {
            int nx = b[i].x + dx[d];
            int ny = b[i].y + dy[d];
            if (inmap(nx, ny) && tmap[nx][ny] == -2) {
                tot++;
            }
        }
        if (tot != b[i].num) return false;
    }
    return true;
}

// 深度优先搜索
void dfs(int v, int tot) {
    if (tot >= ans) return; // 剪枝
    for (int i = v; i < n * m; i++) {
        int x = i / m;
        int y = i % m;
        if (can(x, y)) {
            vis[x][y] = 1;
            dfs(i + 1, tot + 1);
            vis[x][y] = 0;
        }
    }
    if (isok()) {
        ans = min(tot, ans);
    }
}

int main() {
    int t, x, y, v;
    node a;
    while (scanf("%d%d", &n, &m) && (n || m)) {
        int N = n * m;
        b.clear();
        memset(map, -0x3f, sizeof(map));
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = -4; // 初始化为空方格
            }
        }
        scanf("%d", &t);
        for (int i = 1; i <= t; i++) {
            scanf("%d%d%d", &x, &y, &v);
            x--; y--; // 转换为 0-based
            map[x][y] = v;
            if (v != -1) {
                a.x = x;
                a.y = y;
                a.num = v;
                b.push_back(a);
            }
        }
        ans = inf;
        dfs(0, 0);
        if (ans != inf)
            printf("%d\n", ans);
        else
            printf("No solution\n");
    }
    return 0;
}