算法标签

回溯算法 状态枚举 剪枝优化（若后续考虑优化时会用到）

问题分析

给定一个$N*M$的硅片，上面有 $K$ 个坏的单位正方形，目标是切割出尽可能多的2 * 3 或 3 * 2的芯片，且芯片不能包含坏的正方形。由于需要尝试不同的切割方案来找到最大芯片数，所以可以使用回溯算法，枚举所有可能的切割方式。

回溯算法思路

状态表示

可以用一个二维数组来表示硅片，其中每个元素表示对应位置的单位正方形是否为坏的（例如 0 表示好的，1 表示坏的）。同时记录已经切割出的芯片数量。

回溯过程

从硅片的左上角开始，依次遍历每个单位正方形。对于每个单位正方形，尝试两种切割方式：放置一个 2 * 3 的芯片和放置一个 3 * 2 的芯片。在尝试放置芯片时，检查该位置是否满足条件，即芯片所覆盖的单位正方形都是好的（没有坏的）。如果满足条件，则在硅片上标记这几个单位正方形已被使用（例如将对应的数组元素设为 1），然后递归继续处理下一个位置。递归返回后，需要恢复这几个单位正方形的状态（将对应的数组元素设为 0），以便尝试其他切割方案。如果不满足条件，则直接处理下一个位置。当遍历完整个硅片时，记录当前已经切割出的芯片数量，并更新最大芯片数量。

通过上述回溯算法的步骤，能够对给定的硅片进行所有可能的切割尝试，从而找到能够切割出的最大芯片数量，解决题目中要求的问题。

代码实现（c++)

#include <iostream>
#include<cstring> 
using namespace std;

int N, M, k;
int d[2][59049];
int w[12] = {0, 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};
int p[11];
int q[11];
int badSquares[151][11];
int cnt;
int o;

inline int ternary2decimal(int a[]) {
    int sum = 0;
    for (int i = 1; i <= M; ++i) {
        sum += a[i] * w[i];
    }
    return sum;
}
inline void decimal2ternary(int code, int a[]) {
    for (int i = 1; i <=M; ++i) {        
        a[i] = code % 3;
        code /= 3;
    }
}

void dfs(int p[], int q[], int y, int cntNow) {
    int qState = ternary2decimal(q);
    if (cntNow > d[1 - o][qState]) {
        d[1 - o][qState] = cntNow;
    }
    if (cntNow > cnt) {
        cnt = cntNow;
    }
    for (int t = y; t < M; ++t) {
        if (q[t] == 0 && q[t + 1] == 0 && p[t] == 0 && p[t + 1] == 0) {
            q[t] = q[t + 1] = 2;    //放置一块纵向芯片
            dfs(p, q, t + 2, cntNow + 1);    //转至右边第二块
            q[t] = q[t + 1] = 0;
        } else if (t + 2 <= M && q[t] == 0 && q[t + 1] == 0 && q[t + 2] == 0) {
            q[t] = q[t + 1] = q[t + 2] = 2;    //放置一块横向芯片
            dfs(p, q, t + 3, cntNow + 1);    //转至右边第三块
            q[t] = q[t + 1] = q[t + 2] = 0;
        }
    }
}

int main(void) {
    int cases;
    cin >> cases;
    while(cases--) {
        cin >> N >> M >> k;
        memset(d, -1, sizeof(d));
        memset(badSquares, 0, sizeof(badSquares));
        for (int i = 0; i < k; ++i) {
            int x, y;
            cin >> x >> y;
            badSquares[x][y] = 1;
        }    
        for (int i = 1; i <= M; ++i) {
            p[i] = badSquares[1][i] + 1;
            //预先处理第一行的状态，坏点为2，
            //好点为1(可以看做人工加入了全部是坏点的第0行，
            //省去了下边界处理的问题)
        }
        d[0][ternary2decimal(p)] = 0;    //前0行可放芯片数0
        o = 0;
        cnt = 0;
        for (int i = 1; i < N; ++i) {
            memset(d[1 - o], -1, sizeof(d[1 - o]));
            for (int j = 0; j < w[M + 1]; ++j) {
                if (d[o][j] == -1) {
                    continue;
                }
                decimal2ternary(j, p);
                for (int k = 1; k <= M; ++k) {
                    q[k] = p[k] == 0 ? 0 : p[k] - 1;    //推上一行的每格状态
                    if (badSquares[i + 1][k] == 1) {
                        q[k] = 2;    //遇上坏点，状态为2
                    }
                }
                dfs(p, q, 1, d[o][j]);
            }
            o = 1 - o;
        }
        printf("%d\n", cnt);
    }
    system("pause");
    return 0;
}