最优查找网格中可放置指定矩形的最近空闲位置

嗨，这个问题我在做UI布局和网格资源分配的时候碰到过，刚好有几个实用的思路可以分享给你！核心目标是找到离(x,y)最近的、能放下w×h矩形的空闲区域，用C#实现的话，最靠谱的方式是广度优先搜索（BFS），再配合一些优化技巧提升效率，下面给你详细拆解：

因为我们要找“最近”的位置，BFS天生就是按距离层级遍历的——从目标点(x,y)开始，先检查周围1步内的所有可能位置，再扩展到2步、3步……第一个符合条件的位置就是我们要的，比暴力遍历所有位置再排序高效得多。

1. 定义“距离”规则 #

通常用曼哈顿距离（|x1-x2| + |y1-y2|），它符合网格中“移动步数”的直观感受，计算也快。如果需要更精确的“空间距离”，也可以用欧几里得距离，但曼哈顿在网格场景下更实用。

如果你的需求是“矩形任意点到(x,y)的最小距离最近”，而不是矩形左上角的距离，那可以用我后面提到的优先队列方案，计算矩形区域到目标点的最小距离。

2. 合法位置范围校验 #

首先明确：矩形的左上角(px, py)必须满足：

• px + w ≤ 网格宽度
• py + h ≤ 网格高度
  否则矩形会超出网格边界，直接跳过这类候选点。

3. 空闲区域检查 #

对每个候选的(px, py)，需要验证矩形覆盖的所有单元格都是false（空闲）。这里有两种方式：

方式一：暴力遍历（适合小矩形） #

直接遍历矩形范围内的每个单元格，检查是否有true（已占用）：

private bool IsRectFree(bool[,] grid, int startX, int startY, int width, int height)
{
    for (int y = startY; y < startY + height; y++)
    {
        for (int x = startX; x < startX + width; x++)
        {
            if (grid[x, y]) // 碰到已占用区域
                return false;
        }
    }
    return true;
}

方式二：前缀和优化（适合大矩形/频繁检查） #

提前预处理一个前缀和数组，能在O(1)时间内判断任意矩形区域是否有占用：

// 预处理前缀和：sum[i][j] 表示从(0,0)到(i-1,j-1)的已占用单元格数量
private int[,] ComputePrefixSum(bool[,] grid)
{
    int gridWidth = grid.GetLength(0);
    int gridHeight = grid.GetLength(1);
    int[,] sum = new int[gridHeight + 1, gridWidth + 1];

    for (int y = 0; y < gridHeight; y++)
    {
        int rowTotal = 0;
        for (int x = 0; x < gridWidth; x++)
        {
            rowTotal += grid[x, y] ? 1 : 0;
            sum[y + 1, x + 1] = sum[y, x + 1] + rowTotal;
        }
    }
    return sum;
}

// 快速检查矩形是否空闲：区域内已占用数量为0则合法
private bool IsRectFreeFast(int[,] prefixSum, int startX, int startY, int width, int height)
{
    int endX = startX + width;
    int endY = startY + height;
    int occupiedCount = prefixSum[endY, endX] - prefixSum[startY, endX] - prefixSum[endY, startX] + prefixSum[startY, startX];
    return occupiedCount == 0;
}

4. BFS 遍历实现 #

用队列存储候选的左上角位置，按距离层级扩展，同时用visited数组避免重复检查：

public (int x, int y)? FindClosestFreeRect(bool[,] grid, int targetX, int targetY, int rectWidth, int rectHeight)
{
    int gridWidth = grid.GetLength(0);
    int gridHeight = grid.GetLength(1);

    // 先判断矩形本身是否能放进网格
    if (rectWidth > gridWidth || rectHeight > gridHeight)
        return null;

    int maxValidPx = gridWidth - rectWidth;
    int maxValidPy = gridHeight - rectHeight;

    Queue<(int x, int y)> queue = new Queue<(int x, int y)>();
    bool[,] visited = new bool[gridWidth, gridHeight];

    // 先把目标点对应的合法左上角加入队列（如果在范围内）
    if (targetX >= 0 && targetX <= maxValidPx && targetY >= 0 && targetY <= maxValidPy)
    {
        queue.Enqueue((targetX, targetY));
        visited[targetX, targetY] = true;
    }

    // 8个方向扩展（确保覆盖所有曼哈顿距离层级）
    var directions = new (int dx, int dy)[] 
    { 
        (1,0), (-1,0), (0,1), (0,-1),
        (1,1), (1,-1), (-1,1), (-1,-1)
    };

    // 预处理前缀和（如果用快速检查的话）
    var prefixSum = ComputePrefixSum(grid);

    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        int px = current.x;
        int py = current.y;

        // 检查当前位置是否能放下矩形
        if (IsRectFreeFast(prefixSum, px, py, rectWidth, rectHeight))
        {
            return (px, py);
        }

        // 扩展到相邻的候选点
        foreach (var dir in directions)
        {
            int newPx = px + dir.dx;
            int newPy = py + dir.dy;
            if (newPx >= 0 && newPx <= maxValidPx && newPy >= 0 && newPy <= maxValidPy && !visited[newPx, newPy])
            {
                visited[newPx, newPy] = true;
                queue.Enqueue((newPx, newPy));
            }
        }
    }

    // 没有找到可用位置
    return null;
}

如果你的需求是“矩形区域到(x,y)的最小距离最近”（比如目标点在某个矩形内部的话，这个矩形就是最近的），可以用PriorityQueue（C# 6及以上支持），按矩形到目标点的最小距离排序，每次取出距离最小的候选点检查：

// 计算矩形到目标点的最小曼哈顿距离
private int GetMinRectDistance(int targetX, int targetY, int px, int py, int w, int h)
{
    int rectLeft = px;
    int rectRight = px + w - 1;
    int rectTop = py;
    int rectBottom = py + h - 1;

    int dx = 0;
    if (targetX < rectLeft) dx = rectLeft - targetX;
    else if (targetX > rectRight) dx = targetX - rectRight;

    int dy = 0;
    if (targetY < rectTop) dy = rectTop - targetY;
    else if (targetY > rectBottom) dy = targetY - rectBottom;

    return dx + dy;
}

// 用优先队列实现的版本
public (int x, int y)? FindClosestFreeRectByMinDistance(bool[,] grid, int targetX, int targetY, int rectWidth, int rectHeight)
{
    int gridWidth = grid.GetLength(0);
    int gridHeight = grid.GetLength(1);

    if (rectWidth > gridWidth || rectHeight > gridHeight)
        return null;

    int maxValidPx = gridWidth - rectWidth;
    int maxValidPy = gridHeight - rectHeight;

    PriorityQueue<(int x, int y), int> pq = new PriorityQueue<(int x, int y), int>();
    bool[,] visited = new bool[gridWidth, gridHeight];

    // 初始化队列，加入目标点对应的合法位置
    if (targetX >= 0 && targetX <= maxValidPx && targetY >= 0 && targetY <= maxValidPy)
    {
        int distance = GetMinRectDistance(targetX, targetY, targetX, targetY, rectWidth, rectHeight);
        pq.Enqueue((targetX, targetY), distance);
        visited[targetX, targetY] = true;
    }

    var directions = new (int dx, int dy)[] 
    { 
        (1,0), (-1,0), (0,1), (0,-1),
        (1,1), (1,-1), (-1,1), (-1,-1)
    };

    var prefixSum = ComputePrefixSum(grid);

    while (pq.Count > 0)
    {
        var current = pq.Dequeue();
        int px = current.x;
        int py = current.y;

        if (IsRectFreeFast(prefixSum, px, py, rectWidth, rectHeight))
        {
            return (px, py);
        }

        foreach (var dir in directions)
        {
            int newPx = px + dir.dx;
            int newPy = py + dir.dy;
            if (newPx >= 0 && newPx <= maxValidPx && newPy >= 0 && newPy <= maxValidPy && !visited[newPx, newPy])
            {
                visited[newPx, newPy] = true;
                int distance = GetMinRectDistance(targetX, targetY, newPx, newPy, rectWidth, rectHeight);
                pq.Enqueue((newPx, newPy), distance);
            }
        }
    }

    return null;
}

• 坐标系统：确认你的网格是x为列、y为行还是反过来，代码中grid.GetLength(0)是第一维度，要对应调整边界判断。
• 动态网格：如果网格频繁更新（比如经常放置/移除矩形），BFS的方式比预缓存所有空闲位置更合适，因为缓存会频繁失效。
• 性能：当网格非常大时，可以考虑限制搜索的最大距离（比如只找10步内的位置），避免无意义的遍历。

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