检测二维数组中的相干邻居/邻域

Question

我有一个任意的二维数组，每个字段都有一个 id 和一个 teamid（这里用颜色 1 表示）。

我希望每个社区都有一个包含 id 的数组在里面。

一个社区由具有相同 teamid 水平和垂直（不是对角线）邻居的字段组成

例如：这就是我所拥有的：

array[0][0] = {id:1,teamId:1} 
array[1][0] = {id:2,teamId:1} 
array[2][0] = {id:3,teamId:0}
array[3][0] = {id:4,teamId:2}
array[4][0] = {id:5,teamId:2}
array[5][0] = {id:6,teamId:0}

array[0][1] = {id:7,teamId:1} 
array[1][1] = {id:8,teamId:1} 
array[2][1] = {id:9,teamId:1}
array[3][1] = {id:10,teamId:2}
array[4][1] = {id:11,teamId:2}
array[5][1] = {id:12,teamId:0}

//and so on..

这就是我想要的：

neighborhood[1] = [1,2,7,8,9,13,14]
neighborhood[2] = [4,5,10,11]
neighborhood[3] = [16,22,23,24,29,30]
neighborhood[4] = [25,31,32,37,38]
neighborhood[5] = [35,41]

我不是在搜索图像，而是在搜索数组

neighborhood

提前致谢！

Answer 1

您可以使用点和方块游戏中的逻辑。如果玩家用墙将其包围，则该块属于该玩家。因此，除了外部单元之外，每个单元还需要 4 面墙。要测试单元格是否已关闭，您可以使用 4 class 个变量：

var Block = function() {
  this.isclosed=0;
  this.left=0;
  this.top=0;
  this.right=0;
  this.bottom=0;
  return this;
}

Block.prototype = {
  isClosed : function () {
    if (this.isclosed==true) {
      return false;
    } else if (this.left && this.top && this.right && this.bottom) {
      this.isclosed=true;
      return true;
    } else {
      return this.left && this.top && this.right && this.bottom;
    }
  }
}

您可以试试我的点和块游戏实现 @ https://dotsgame.codeplex.com/。

Answer 2

解决该问题的方法参考Connected Component Labelling

有人问过一次similar question，我从中得到了解决方案：

// matrix dimensions
var row_count = 20;
var col_count = 20;
var numOfTeams = 2;

// the input matrix
var m = [];
// the labels, 0 means unlabeled
var label = [];
var source = document.getElementById("source");
for (var i = 0; i < row_count; i++) {
  var row = source.insertRow(0);
  m[i] = [];
  label[i] = [];
  for (var j = 0; j < col_count; j++) {
    //m[i][j] = Math.round(Math.random());
    m[i][j] = getRandomInt(0, numOfTeams + 1);
    label[i][j] = 0;
    var cell1 = row.insertCell(0);
    cell1.innerHTML = m[i][j];
  }
}

// direction vectors
var dx = [1, 0, -1, 0];
var dy = [0, 1, 0, -1];

function dfs(x, y, current_label, team) {
  if (x < 0 || x == row_count) return; // out of bounds
  if (y < 0 || y == col_count) return; // out of bounds
  if (label[x][y] || team != m[x][y]) return; // already labeled or not marked with 1 in m


  // mark the current cell
  label[x][y] = current_label;

  // recursively mark the neighbors
  for (var direction = 0; direction < 4; ++direction) {
    dfs(x + dx[direction], y + dy[direction], current_label, team);
  }
}


function find_components() {
  var component = 0;

  for (var i = 0; i < row_count; ++i) {
    for (var j = 0; j < col_count; ++j) {

      if (!label[i][j] && m[i][j]) dfs(i, j, ++component, m[i][j]);
    }
  }
}

find_components();

var result = document.getElementById("result");


for (var i in label) {
  var string = ""
  var row = result.insertRow(0);
  for (var j in label[i]) {
    string += label[i][j] + " "
    var cell1 = row.insertCell(0);
    cell1.innerHTML = label[i][j];
  }
}

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

table tr td {
  min-width: 14px
}

<div style="float:left">
  <table id="source"></table>
</div>
<div style="float:right">
  <table id="result"></table>
</div>

检测二维数组中的相干邻居/邻域

Detect coherent neighbors / neighborhood in 2d array

javascript

arrays

neighbours