本文介绍一种基于贪心策略与实时约束检查的网格着色算法，通过动态筛选可用颜色、规避上下左右相邻冲突，实现多色资源在二维表格中的无邻色重复分配。
本文介绍一种基于贪心策略与实时约束检查的网格着色算法，通过动态筛选可用颜色、规避上下左右相邻冲突，实现多色资源在二维表格中的无邻色重复分配。
在构建如“题册分发”类应用时（例如为学生随机分配不同颜色的练习册），仅靠全局洗牌后顺序填充无法保证空间局部约束——即任意两个上下或左右相邻的单元格不得同色。原始代码中 colors.pop() 的线性分配方式忽略了邻域依赖关系，极易导致视觉上扎眼的连续同色块。要真正满足“无相邻同色”这一核心条件，必须将颜色选择逻辑从事后洗牌升级为逐格决策+实时校验。
核心思路：逐行逐列贪心填充 + 邻域感知筛选
我们采用行优先遍历（row-major order），对每个单元格 (row, col) 执行以下步骤：
- 识别已占用邻格：仅需检查左侧（同一行前一列） 和 上方（上一行同列） 单元格——因按序填充，右侧与下方尚未赋值，无需考虑；
- 动态生成可用颜色池：从剩余颜色列表中过滤掉 leftColor 和 topColor（若存在），得到 availableColors；
- 可行性判断与回退：若 availableColors.length === 0，说明当前资源配置下无法满足约束，立即终止并提示用户调整输入（如增加某颜色数量或减少总格数）；
- 随机选取并消耗：从 availableColors 中随机选一个颜色赋给当前单元格，并从全局 colors 数组中移除该颜色，确保资源不重复使用。
以下是优化后的关键逻辑实现（兼容原HTML结构）：
function distributeBooks() {
const rows = parseInt(document.getElementById("rows").value) || 0;
const cols = parseInt(document.getElementById("cols").value) || 0;
const whiteCount = parseInt(document.getElementById("whiteCount").value) || 0;
const pinkCount = parseInt(document.getElementById("pinkCount").value) || 0;
const greenCount = parseInt(document.getElementById("greenCount").value) || 0;
const yellowCount = parseInt(document.getElementById("yellowCount").value) || 0;
const totalCells = rows * cols;
let colors = [];
// 构建初始颜色池（注意：此处用数组而非对象，便于splice操作）
colors.push(...Array(whiteCount).fill("white"));
colors.push(...Array(pinkCount).fill("pink"));
colors.push(...Array(greenCount).fill("green"));
colors.push(...Array(yellowCount).fill("yellow"));
if (colors.length < totalCells) {
alert("颜色总数不足，请增加各颜色数量！");
return;
}
const table = document.getElementById("distributionTable");
table.innerHTML = "";
// 逐行逐列填充
for (let row = 0; row < rows; row++) {
const tr = document.createElement("tr");
for (let col = 0; col < cols; col++) {
const td = document.createElement("td");
// 获取左侧与上方已填色（若存在）
const leftColor = col > 0 ? tr.children[col - 1].className : null;
const topColor = row > 0 ? table.children[row - 1].children[col].className : null;
// 筛选当前可用颜色（排除左、上冲突色）
const availableColors = colors.filter(
color => color !== leftColor && color !== topColor
);
// 检查是否可解
if (availableColors.length === 0) {
alert("当前颜色配比无法避免相邻同色，请调整输入！");
return;
}
// 随机选取一个可用颜色
const randomIndex = Math.floor(Math.random() * availableColors.length);
const selectedColor = availableColors[randomIndex];
td.className = selectedColor;
// 从总池中移除已用颜色
const idxInColors = colors.indexOf(selectedColor);
colors.splice(idxInColors, 1);
tr.appendChild(td);
}
table.appendChild(tr);
}
}注意事项与优化建议
- ✅ 仅需检查左/上两邻格：因按 row→col 顺序填充，右、下邻格必为空，无需验证；
- ⚠️ 资源消耗不可逆：splice() 直接修改原数组，确保每种颜色严格按输入数量分配；
- ? 增强随机性：若希望结果更均匀（避免末期因颜色枯竭导致模式化），可在每次筛选前对 availableColors 进行二次洗牌（调用 shuffleArray(availableColors)）；
- ? 扩展性提示：当前支持4色，如需支持更多颜色，只需扩展输入字段并追加 colors.push(...Array(n).fill("colorName"))；
- ❗ 理论边界：根据图论四色定理，平面网格最多需4色即可无邻同色；但若某单一颜色占比过高（如 >50%），仍可能因局部密度触发 availableColors 为空——此时算法主动报错，引导用户优化配比。
该方案兼顾确定性约束保障与视觉随机性，无需回溯或复杂搜索，时间复杂度为 O(rows × cols × C)，C 为平均可用颜色数，在常规题册规模（≤20×20）下性能优异且逻辑清晰可靠。
