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

This is an issue in typescript. As such, I have a variable with various string entries in the form of x, y position. ["3,3","3,4","3,5","2,3","2,4","2,5","-1,-2","-2,- 2","-2,-1"] I want to know if this piece of land is one piece or several pieces.

CodePudding user response：

Establish the mathematical guidelines

Two tiles are neighbors if they are different by a value of 1 in either x or y (but not both).

If you only need to determine whether they are all connected, then you really need to determine that every pair of vertices have a path from one to the other.

Plan the coding implementation

One way to go about this is to create an empty land mass array, start by adding a single tile from the source array, then you add each tile in the source array to the land mass array if it is a neighbor to one of the items in the land mass. If it does not have a neighbor, it may just not have one on the land mass yet, so we add it to a deferred queue and return to those when we have exhausted the source.

This method has O(n^2) complexity, but maybe someone else has a better solution computationally.

Give it a try

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;