我有一个难题要解决，其中涉及采用网格大小的输入。网格总是正方形的。然后提供网格上的一些点，如果网格上的正方形紧邻左侧或右侧或上方或下方，则“采用”这些方 block 。
例如想象一个 10 x 10 的网格。如果点是 (1,1) 左下角和 (10,10) 右上角，那么如果给定点 (2,1) 则左右方格位置(10 个方格) 以及上方和下方(另外 9 个正方形)被占用。因此，使用简单的算法，如果网格是 n 平方的，那么将在提供的第一个点上采用 n + (n-1) 个正方形。
但如果提供其他点作为输入，事情就会变得复杂。例如，如果下一个点是(5,5)，那么将“采用”另外 19 个正方形减去与其他点重叠的正方形。所以它变得复杂。当然，可以提供重叠更多的点，例如 (3,1)。
是否有解决此类问题的算法？
或者它只是保存一个二维数组并为每个获取的正方形放置一个 x 的问题。然后最后只是计算已占用(或未占用)的方 block 。那行得通，但我想知道是否有更简单的方法。
最佳答案
保留两组:X(存储所有 x 坐标)和 Y(存储所有 y 坐标)。所取的方 block 数将为 n * (|X| + |Y|) - |X| * |是|。这是因为每个唯一的 x 坐标删除一列 n 个方 block ，每个唯一的 y 坐标删除一行 n 个方 block 。但这会将删除的行和列的交集计算两次，所以我们减去 |X| * |是|对此负责。
关于algorithm - 网格 'used' 上的位置，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20806620/