题解 | 小心火烛的歪

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
const tokens: string[] = [];
rl.on("line", function (line) {
  tokens.push(line.trim());
}).on("close", function () {
  const [n, m, q] = tokens.shift().split(" ").map(Number);
  const ground: number[][] = [];
  for (let i = 0; i < n; ++i) {
    ground.push(tokens.shift().split("").map(Number));
  }
  if (isAllOnes(ground, n, m)) {
  	/** 草地全为杂物, 选零个计划 */
    console.log(0);
  } else {
  	/** 把计划全挑出来 */
    const plans: number[][][] = [];
    while (tokens.length !== 0) {
      const plan: number[][] = [];
      let i = 0;
      while (i < n) {
        plan.push(tokens.shift().split("").map(Number));
        ++i;
      }
      plans.push(plan);
    }
    let count = -1,
      planCodes: number[] = [],
      minPlans = Number.MAX_VALUE;
	/** 从第一个计划开始遍历 */
    for (let i = 0; i < q; ++i) {
      if (isValidPlan(plans[i], ground, n, m)) { // 该计划符合要求，进行下一步处理
	  	/** 初始化一个空计划 */
        let tmpGround: number[][] = Array.from({ length: n }, () =>
            Array(m).fill(0)
          ),
          tmpPlanCodes: number[] = [i + 1]; // 添加第一个符合要求的计划编号
        addPlan(plans[i], tmpGround, n, m); // 把第一个符合要求的计划添加进来
        let tmpCount = 1, // 已选择的计划数量为 1
          j = i + 1;
		/** 挑选后续合格的计划，直到把原草地的空地填满为止 */
        while (j < q && !isValidResolvedGround(tmpGround, ground, n, m)) {
          if (isValidPlan(plans[j], ground, n, m)) {
            addPlan(plans[j], tmpGround, n, m);
            tmpPlanCodes.push(j + 1);
            ++tmpCount;
          }
          ++j;
        }
        if (isValidResolvedGround(tmpGround, ground, n, m)) {
          i = --j;
          /** 去重 把多余的计划减掉*/
          for (let k = 0; k < tmpPlanCodes.length; ++k) {
            removePlan(plans[tmpPlanCodes[k] - 1], tmpGround, n, m);
            if (isValidResolvedGround(tmpGround, ground, n, m)) {
			//减掉该计划后，依然满足要求，把该计划编号从已挑选列表中删除, 计划数减 1
              tmpPlanCodes.splice(k, 1);
              --k;
              --tmpCount;
            } else {
			// 减掉该计划后不满足要求，把它重新添加回来
              addPlan(plans[tmpPlanCodes[k] - 1], tmpGround, n, m);
            }
          }
          if (tmpCount < minPlans) {
            planCodes = tmpPlanCodes;
            count = minPlans = tmpCount;
          }
        }
      }
    }
    console.log(count);
    console.log(planCodes.join(" "));
  }
});
function isAllOnes(ground: number[][], n: number, m: number): boolean {
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < m; ++j) {
      if (ground[i][j] === 0) return false;
    }
  }
  return true;
}
function isValidPlan(
  plan: number[][],
  ground: number[][],
  n: number,
  m: number
): boolean {
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < m; ++j) {
      if (plan[i][j] === 1 && ground[i][j] === 1) return false;
    }
  }
  return true;
}
/** 之所以用数字累加的方式，是为了方便后续处理去重逻辑 */
function addPlan(
  plan: number[][],
  resolvedGround: number[][],
  n: number,
  m: number
) {
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < m; ++j) {
      resolvedGround[i][j] += plan[i][j];
    }
  }
}
function removePlan(
  plan: number[][],
  resolvedGround: number[][],
  n: number,
  m: number
) {
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < m; ++j) {
      resolvedGround[i][j] -= plan[i][j];
    }
  }
}
/** 检查已挑选计划处理过后的草地，在原草地的空地上对应的值是否大于 0，如果依然为 0，说明这些计划还不足以解决 */
function isValidResolvedGround(
  resovedGround: number[][],
  ground: number[][],
  n: number,
  m: number
): boolean {
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < m; ++j) {
      if (ground[i][j] === 0 && resovedGround[i][j] === 0) return false;
    }
  }
  return true;
}