土地地图数组中判断这是否是一块土地的问题

Question

这是打字稿中的一个问题。因此，我有一个变量，其中包含 x、y 位置形式的各种字符串条目。 ["3,3","3,4","3,5","2,3","2,4","2,5","-1,-2","-2,- 2","-2,-1"] 我想知道这块地是一块还是几块

Answer 1

建立数学准则

如果两个图块在 x 或 y（但不是两者）上相差 1，则它们是相邻的。

如果你只需要判断它们是否都连通，那么你真的need to determine that every pair of vertices have a path from one to the other。

规划编码实现

解决这个问题的一种方法是创建一个空的地块数组，首先从源数组中添加一个瓦片，然后将源数组中的每个瓦片添加到地块数组中（如果它是相邻的）到土地中的一项。如果它没有邻居，它可能只是在陆地上还没有邻居，所以我们将它添加到延迟队列中，并在我们耗尽资源时将其添加到延迟队列中return。

此方法的复杂度为 O(n^2)，但也许其他人在计算上有更好的解决方案。

试试看

let source = [...coordinateArray]; // from prop or API or wherever
let landMass = [];
let deferred = [];

while(source.length) {
  // add the tile if it has a neighbor on the land mass
  // defer the tile if it does not have a neighbor on the land mass
  source.forEach(pair1 => {
    const [x1, y1] = pair1.split(",");
    const hasNeighbor = !landMass.length || landMass.some(pair2 => {
      const [x2, y2] = pair2.split(",");
      
      // return "true" if off by 1 in x or y position and 0 in the other
      return (Math.abs(x1 - x2) === 1 && y1 === y2) || (Math.abs(y1 - y2) === 1 && x1 === x2);
    });

    // push tile to landMass or to defer queue
    if(hasNeighbor) {
      landMass.push(pair1);
    } else {
      deferred.push(pair1);
    }
  });

  // if source is now the same as deferred, 
  // then nothing was added to the land mass
  // therefore it is disconnected and we can break out
  if(source.length === deferred.length) {
    break;
  }

  // otherwise, we have exhausted the source, 
  // so we move the "deferred" to the "source"
  // and empty the "deferred" to repeat
  source = [...deferred];
  deferred = [];

  // if the deferred queue had length 0, 
  // then we will break out of the while loop
}

// if the source has length > 0, then some tiles could not be mapped
// in that case, it is disconnected
// if the source has no length, then everything was mapped to the land mass
// in that case, it is connected
const allTilesAreConnected = !source.length;

土地地图数组中判断这是否是一块土地的问题

The problem of determining whether this is a piece of land in land map array

tiles

node.js

typescript

reactjs