在二维矩阵中捕捉数字2的最短路径

Question

在二维矩阵中捕捉数字2的最短路径

3

我需要从矩阵中的 1 所在位置开始，找到移动到达 2 时需要移动的空间数 (上, 左, 右, 下)。同时，您可以沿着矩阵的一侧绕回到另一侧。因此，下面的示例应返回2，因为需要先向左移动1，然后向下移动1。我完全陷入了困境。

var ARR = [
    [0, 0, 0, 0],
    [1, 0, 0, 0],
    [0, 0, 0, 2],
    [0, 0, 0, 0]
  ],
  ONE, TWO;

for (x in ARR) {
  for (y in ARR[x]) {
    if (ARR[x][y] == 1) {
      ONE = [x, y];
    }
    if (ARR[x][y] == 2) {
      TWO = [x, y];
    }
  }
}

document.body.innerHTML = Math.abs(ONE[0] - TWO[0]) - Math.abs(ONE[1] - TWO[1]);

- CeeJay

我不太明白你在这个参数中所说的返回2个空格是什么意思。难道它不应该返回4吗？因为数字1必须向右移动3次并向下移动1次才能到达数字2。 - UchihaItachi

@UchihaItachi 它也可以移动到矩阵的另一侧。只需按照以下路径：1-向左和向下移动。它将出现在右侧并向下移动。 - CeeJay

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dwij · Answer 1

请查看以下解决方案。在此解决方案中，无需硬编码任何值。您只需更改矩阵即可。

这里是用于测试的fiddle。

var ARR = [
    [0, 0, 0, 0],
    [1, 0, 0, 0],
    [0, 0, 0, 2],
    [0, 0, 0, 0]
  ],
  ONE, TWO;

for (x in ARR) {
  for (y in ARR[x]) {
    if (ARR[x][y] == 1) {
      ONE = [x, y];
    }
    if (ARR[x][y] == 2) {
      TWO = [x, y];
    }
  }
}

var width = ARR[0].length;
var height = ARR.length;

//get two methods of reaching via y axis
var upDown1 = Math.abs(ONE[0] - TWO[0]);
var upDown2 = height - Math.abs(ONE[0] - TWO[0]);

//get two methods of reaching via x axis
var leftRight1 = Math.abs(ONE[1] - TWO[1]);
var leftRight2 = width - Math.abs(ONE[1] - TWO[1]);

//get the minimum space counts of above methods in y and x axis
var minUpDown = Math.min(upDown1,upDown2);
var minLeftRight = Math.min(leftRight1,leftRight2);

 
document.body.innerHTML = minUpDown+minLeftRight;

- Qwerp-Derp · Answer 2

你在问题介绍中说板子本身“环绕”-也就是说，你可以从最左边向左走，最终到达右边，但你的逻辑没有考虑到这一点，因为你只检查距离而不考虑环绕。

以下是一个有效的解决方案：

// Constants for the array, as well as the
// width and height of the array
const arr = [
  [0, 0, 0, 0, 0],
  [1, 0, 0, 0, 0],
  [0, 0, 0, 0, 2],
  [0, 0, 0, 0, 0]
];
const width = arr[0].length,
      height = arr.length;

// Stores the position of the "1" and "2"
let one, two;
// Horizontal and vertical distances between
// the "1" and "2"
let dist_x, dist_y;

// Figure out where the "1" and "2" is
for (let x in arr) {
  for (let y in arr[x]) {
    if (arr[x][y] === 1) {
      one = [x, y];
    } else if (arr[x][y] === 2) {
      two = [x, y];
    }
  } 
}

// Sets the horizontal and vertical distances
// between the two numbers
dist_x = Math.abs(one[1] - two[1]);
dist_y = Math.abs(one[0] - two[0]);

// If the distance is longer than half the size of
// the board in either direction, we go the other way
// instead.
if (dist_x > width / 2) {
  dist_x = width - dist_x;
}

if (dist_y > height / 2) {
  dist_y = height - dist_y;
}

console.log(dist_x + dist_y);

- IAmCoder · Answer 3

如果你先计算出向右移动的步骤，然后是向下移动的步骤，那么它会变得更容易：

var ARR = [
    [0, 0, 0, 0],
    [1, 0, 0, 0],
    [0, 0, 0, 2],
    [0, 0, 0, 0]
  ],
  ONE, TWO;

for (x in ARR) {
  for (y in ARR[x]) {
    if (ARR[x][y] == 1) {
      ONE = [x, y];
    }
    if (ARR[x][y] == 2) {
      TWO = [x, y];
    }
  }
}

var xSteps = Math.abs(ONE[0] - TWO[0]);
if (xSteps === 3) // then you can also do it in one by going the other direction
{
    xSteps = 1;
}

var ySteps = Math.abs(ONE[1] - TWO[1]);
if (ySteps === 3) // then you can also do it in one by going the other direction
{
    ySteps = 1;
}


document.body.innerHTML = "X steps: " + xSteps + ", Y steps: " + ySteps + ", total steps:" + (xSteps + ySteps);

如果您的矩阵大小是可变的，不总是4 x 4，则硬编码检查3需要更改为（矩阵大小的一半+1）...