热门文章
 当前位置：技术文章 > 编程面试题 >

在2D网格上查找最近物体的算法

问题内容：

假设您有一个2D网格，该网格上的每个点都有x个对象（x> = 0）。我在考虑一种 干净的
算法时遇到了麻烦，因此当用户指定一个坐标时，该算法会找到带有对象的最接近坐标（包括指定的坐标）。

为了简单起见，我们假设如果2个坐标相距相同的距离，则将返回第一个坐标（或者，如果您的算法不能按这种方式工作，那么最后一个坐标就没有关系）。

编辑：离开1的坐标必须是1上，下，左或右。对角线离开的坐标为2。

附带说明一下，什么是算法的免费在线参考？


问题答案：

更新资料

带有新信息：

假设对角坐标为2

该算法将起作用。该算法以螺旋形式向外搜索，以测试从内部开始的每个“环”中的每个点。

请注意，它不会处理超出范围的情况。因此，您应该更改此设置以适合您的需求。

int xs, ys; // Start coordinates

// Check point (xs, ys)

for (int d = 1; d<maxDistance; d++)
{
    for (int i = 0; i < d + 1; i++)
    {
        int x1 = xs - d + i;
        int y1 = ys - i;

        // Check point (x1, y1)

        int x2 = xs + d - i;
        int y2 = ys + i;

        // Check point (x2, y2)
    }


    for (int i = 1; i < d; i++)
    {
        int x1 = xs - i;
        int y1 = ys + d - i;

        // Check point (x1, y1)

        int x2 = xs + i;
        int y2 = ys - d + i;

        // Check point (x2, y2)
    }
}

旧版

假设在2D网格中（0，0）和（1，0）之间的距离与（0，0）和（1，1）相同。该算法将起作用。该算法以螺旋形式向外搜索，以测试从内部开始的每个“环”中的每个点。

请注意，它不会处理超出范围的情况。因此，您应该更改此设置以适合您的需求。

int xs, ys; // Start coordinates

if (CheckPoint(xs, ys) == true)
{
    return (xs, ys);
}

for (int d = 0; d<maxDistance; d++)
{
    for (int x = xs-d; x < xs+d+1; x++)
    {
        // Point to check: (x, ys - d) and (x, ys + d) 
        if (CheckPoint(x, ys - d) == true)
        {
            return (x, ys - d);
        }

        if (CheckPoint(x, ys + d) == true)
        {
            return (x, ys - d);
        }
    }

    for (int y = ys-d+1; y < ys+d; y++)
    {
        // Point to check = (xs - d, y) and (xs + d, y) 
        if (CheckPoint(x, ys - d) == true)
        {
            return (xs - d, y);
        }

        if (CheckPoint(x, ys + d) == true)
        {
            return (xs - d, y);
        }
    }
}