--- 获取不同象限的X循环范围
local function CalculateXRange(directions, x, width)
    local rightFactor = directions[1][1]
    return x, x + width * rightFactor - 1, rightFactor
end

--- 获取不同象限的Y循环范围
local function CalculateYRange(directions, y, height)
    local upFactor = directions[4][2]
    return y, y + height * upFactor - 1, upFactor
end

--- 根据方向、起始位置、占地面积循环遍历
--- @param action fun(i: number, j: number)
local function ForEachRange(directions, x, y, width, height, action)
    local startX, targetX, widthFactor = CalculateXRange(directions, x, width)
    local startY, targetY, heightFactor = CalculateYRange(directions, y, height)
    for i = startX, targetX, widthFactor do
        for j = startY, targetY, heightFactor do
            action(i, j)
        end
    end
end

--- 当前索引是否有效
local function isValidIndex(grid, x, y)
    return x >= 1 and x <= #grid and y >= 1 and y <= #grid[x]
end

--- 当前位置是否有效
local function isValidArea(grid, directions, x, y, width, height)
    if not isValidIndex(grid, x, y) or not isValidIndex(grid, x + width - 1, y + height - 1) then
        return false
    end
    local result = true
    ForEachRange(directions, x, y, width, height, function(i, j)
        if not grid[i][j] then
            result = false
        end
    end)
    return result
end

local directionOrder = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1 } } -- Right, Down, Left, Up

--- 计算启发式分数
local function EvaluateScore(index, startX, startY, x, y, width, height)
    local factorScore = index * 0.2
    local distance1 = (startX - width - x) ^ 2 + (startY - y) ^ 2
    local distance2 = (startX + width - x) ^ 2 + (startY - y) ^ 2
    local distance3 = (startX - x) ^ 2 + (startY - height - y) ^ 2
    local distance4 = (startX - x) ^ 2 + (startY + height - y) ^ 2
    return math.min(distance1, distance2, distance3, distance4) + factorScore
end

local function Search(grid, directions, queue, visited, width, height, startX, startY)
    local result = nil
    local baseScore = math.huge
    while #queue > 0 do
        count = count + 1
        local current = table.remove(queue, 1)
        local x, y, distance = current[1], current[2], current[3]

        for index, direction in ipairs(directions) do
            local newX = x + direction[1]
            local newY = y + direction[2]
            if isValidIndex(grid, newX, newY) and not visited[newX][newY] then
                visited[newX][newY] = true
                table.insert(queue, { newX, newY, distance + 1 })

                if isValidArea(grid, directions, newX, newY, width, height) then
                    local score = EvaluateScore(index, startX, startY, newX, newY, width, height)
                    if score < baseScore then
                        baseScore = score
                        result = { newX, newY }
                    end
                end
            end
        end
    end
    return result
end