按数量种连通作物：Hamiltonian蛇形路径连续分段

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 每格种一个crop，counts非负整数且总数等于格数；正count作物必须四邻接连通，0count不出现。
• 两square训练为上下左对齐，或左右上对齐；不重叠且接壤，无洞。错位/仅角接/其他形状不保证相同构造可行。

解题路线

1. 矩形逐行交替左右扫，形成每格恰一次且相邻的Hamiltonian路径。把路径按每种count切连续段，段内沿路径必连通。
2. 上下square：上块蛇形起始方向依据行数奇偶选，让最后格落在左端；下块第一行从左端向右，跨边界两点竖直相邻。下块再普通蛇形。
3. 左右上对齐用上下方案转置坐标。不独立填两个square后随意分配作物，否则跨块作物可能两部分不相邻。任意多连通形状未必有Hamiltonian路径，不能泛化。

手动走一遍

2×3矩形路径(0,0),(0,1),(0,2),(1,2),(1,1),(1,0)，counts[4,2]让首crop四格连通、后crop两格相邻。上3×3下2×2，上块最后到(2,0)，下块首格(3,0)，跨尺寸仍连续。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def arrange(rows,cols,counts):
    if rows<=0 or cols<=0:raise ValueError("positive dimensions required")
    cells=[(r,c) for r in range(rows) for c in (range(cols) if r%2==0 else range(cols-1,-1,-1))]
    return fill(cells,counts)


def joined_squares(n,m,counts,horizontal=False):
    if n<=0 or m<=0:raise ValueError("positive side lengths required")
    cells=[]
    for r in range(n):
        # End the last row of the upper square at column zero.
        rightward=(r%2)==(n%2)
        cells.extend((r,c) for c in (range(n) if rightward else range(n-1,-1,-1)))
    for r in range(m):
        cells.extend((n+r,c) for c in (range(m) if r%2==0 else range(m-1,-1,-1)))
    if horizontal:cells=[(c,r) for r,c in cells]
    return fill(cells,counts)


def fill(cells,counts):
    if any(type(x) is not int or x<0 for x in counts) or sum(counts)!=len(cells):raise ValueError("counts must fill garden exactly")
    result={};i=0
    for crop,count in enumerate(counts):
        for _ in range(count):result[cells[i]]=crop;i+=1
    return result

复杂度

G格，构造/填充O(G+k)时间，当前代码cells+result O(G)空间；生成器可省cells但输出仍Ω(G)。

易错点与追问

容易失分的边界

• 交界端点落在窄square之外会断路，需要按奇偶选上块方向。
• 对角相邻不算connected。

继续深挖

• 作物要求近矩形或最小周长，为什么连续分段不保证优化？
• 带障碍的连通garden，哪些形状能保证路径存在？