矩形与L型块填充棋盘问题：现有实现思路遇阻求指导

问题明确 #

给定10个矩形/L型拼图块、10个矩形棋盘，需按规则填充并输出所用块顺序，无法填满则输出NONE。规则细节：

1. 块按面积从大到小放置，面积相同优先选宽度更大的块；
2. 第一块放棋盘左下角，后续块放最靠下、最靠左的可放置位置；
3. 重复操作直至棋盘填满或无可用块。

块的表示规则：

• 矩形块：2位数字串（宽+高）
• L型块：3位数字串（宽+垂直部分高度+垂直部分宽度，底座高度固定为1）

输入输出要求：

• 输入共11行：首行是10个块，后10行是棋盘宽高（前5个仅用矩形块，后5个可用L型块）
• 输出每个棋盘的填充块顺序，无法填满输出NONE

你之前尝试用宽×高的布尔二维数组标记已占用区域的思路本身可行，大概率是逻辑细节出错，以下是具体修正和实现提示：

核心解决步骤与提示 #

1. 修正棋盘状态标记逻辑 #

• 坐标体系对齐：定义棋盘左下角为坐标原点(0,0)，x轴向右对应宽度方向，y轴向上对应高度方向，贴合“最靠下最靠左”的查找逻辑；
• 区域检查与标记：
  • 放置块前，必须检查目标区域内所有格子是否未被占用（布尔值为False），不能仅检查起始点；
  • 放置后准确标记对应区域：
    • 矩形块（w×h）：将(x,y)到(x+w-1, y+h-1)的矩形区域全部设为True；
    • L型块：先明确形状——底座为宽×1的矩形，垂直部分为垂直宽度×垂直高度的矩形（默认连接在底座右端），总面积为宽×1 + 垂直宽度×垂直高度，再分别标记底座和垂直部分的区域，确保无越界、无重叠。

2. 块的预处理排序 #

• 先按规则对可用块排序：
  • 计算每个块的面积：矩形块为宽×高，L型块为宽×1 + 垂直部分高度×垂直部分宽度；
  • 排序优先级：先按面积降序，面积相同则按块的宽度（矩形块取第一位数字，L型块取第一位数字）降序；
  • 前5个棋盘需过滤掉L型块，仅对矩形块排序。

3. 可放置位置查找逻辑 #

每次放置块前，严格按以下顺序遍历找位置：

• 遍历顺序：从y=0到棋盘高度-1（从下到上），x=0到棋盘宽度-1（从左到右）；
• 位置校验：
  • 矩形块：检查x + 宽 ≤ 棋盘宽度、y + 高 ≤ 棋盘高度，且区域内所有格子未被占用；
  • L型块：先计算整体占用的边界范围，确认不超出棋盘，再检查所有涉及格子是否未被占用；
• 找到第一个符合条件的位置后，立即放置块、标记区域，并将该块加入结果序列。

4. 终止条件判断 #

• 每次放置后，检查布尔数组是否全为True（棋盘填满），若是则终止并输出结果序列；
• 若遍历完所有可用块仍无法放置，且棋盘未填满，则输出NONE。

5. 常见错误排查 #

• 坐标方向搞反：比如将y轴设为向下，导致“最靠下”位置查找错误；
• L型块区域计算错误：垂直部分的位置或尺寸计算偏差，导致越界或占用已填充区域；
• 排序逻辑错误：面积计算错误，或面积相同时宽度排序方向搞反；
• 放置校验不严谨：仅检查起始点是否为空，未验证整个块的区域是否可用。

内容的提问来源于stack exchange，提问作者Henry Deng