连连看：折不过两弯的那条线

local ok = LinkPath.Find(a, b, 2)   -- 最多两个转弯

fx-linkup

local LinkPath = {}
local KEY = { MAX_TURN = 2 }

-- 扩展网格: 棋盘外圈一圈也算可走, 支持绕外框连线
local function Walkable(grid, r, c, R, C)
    if r == 0 or c == 0 or r == R or c == C then return true end
    return grid[r] == nil or grid[r][c] == nil
end

function LinkPath.Find(grid, a, b)
    local R, C = #grid + 2, #grid[1] + 2
    local start = { r = a.r + 1, c = a.c + 1, turns = -1, dir = -1 }
    local goal = { r = b.r + 1, c = b.c + 1 }
    local queue = { start }
    local best = nil
    local dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }
    while #queue > 0 do
        local cur = table.remove(queue, 1)
        if cur.r == goal.r and cur.c == goal.c then
            if not best or cur.turns < best.turns then best = cur end
        else
            for d = 1, 4 do
                local nr, nc = cur.r + dirs[d][1], cur.c + dirs[d][2]
                if nr >= 0 and nc >= 0 and nr <= R and nc <= C then
                    local isGoal = nr == goal.r and nc == goal.c
                    if isGoal or Walkable(grid, nr, nc, R, C) then
                        local nt = cur.turns + (cur.dir >= 0 and cur.dir ~= d and 1 or 0)
                        if nt <= KEY.MAX_TURN and (not best or nt < best.turns) then
                            local node = { r = nr, c = nc, turns = nt, dir = d,
                                           prev = cur }
                            queue[#queue + 1] = node
                        end
                    end
                end
            end
        end
    end
    -- 回溯路径
    if not best then return nil end
    local path = {}
    local node = best
    while node do
        path[#path + 1] = { r = node.r - 1, c = node.c - 1 }
        node = node.prev
    end
    return path
end

return LinkPath