javascript - 查找网格上的坐标(二维数组)

Question

我目前正在尝试解决在白板模拟面试中未能解决的问题。我被卡住了几次。如有任何帮助，我们将不胜感激。

问题的措辞如下:

Given an NxN grid with an array of lamp coordinates. Each lamp provides illumination to every square on their x-axis, every square on their y-axis, and every square that lies in their diagonal (think of the Queen in chess). Given an array of query coordinates, determine whether that point is illuminated or not.

The catch is when checking a query, all lamps adjacent to or on that query gets turned off. If you visit a coordinate/cell, turn off all lamps that are in that coordinates or adjacent. Two cells are adjacent if they share the same edge or corner.

• write a function checkLampIllumination(N, lamps, queries)
• N : size of the grid
• lamps : coordinates of a lamp
• queries : coordinates on the grid to be checked if they are lit or not

我得到的测试用例是:

N = 8

lamps = [
    [1,6],
    [5,6],
    [7,3],
    [3,2]
]

queries = [
    [4,4],
    [6,6],
    [8,1],
    [3,2],
    [2,3]
]

输出:

['DARK','LIGHT','DARK','DARK','LIGHT']

第二个测试用例:

checkLampIllumination(8, [[4,3],[4,4]], [[3,4],[7,6]])

N = 8

lamps = [
    [4,3],
    [4,4]
]

queries = [
    [3,4],
    [7,6]
]

输出:

['DARK','LIGHT']

这是我目前的尝试。我认为当前的解决方案只是创建网格。我真的不知道该去哪里。

const checkLampIllumination=(N, lamps, queries) => {
    var gridNxN = []
    var row = []
    for (var i = 1; i < 100; i++) {
        if (i.toString().indexOf('0') !== -1) {
            row.push(i)
            gridNxN.push(row)
            row = []
        } else {
            row.push(i)
        }
    }
}

Answer 1

为了实现灯的可视化和查询，您可以使用 pixel art generator如果你愿意的话。

我首先创建一个辅助函数 isAdjacent 来检查两个点是否相邻。然后，迭代每个查询(目标方 block )，并检查是否有灯照亮目标。问题简化为检查:

• 灯不相邻，并且至少满足以下条件之一:

• 灯具有相同的 X 坐标，或者

• 相同的 Y 坐标，或

• 它们位于同一对 Angular 线上，可以通过查看灯和目标的 X 坐标之间的差值是否等于灯和目标的 Y 坐标之间的差值来检查。

将其放入代码中，您将得到:

let lamp = [
  [1, 6],
  [5, 6],
  [7, 3],
  [3, 2]
];
const queries = [
  [4, 4],
  [6, 6],
  [8, 1],
  [3, 2],
  [2, 3]
]

const isAdjacent = (x1, y1, x2, y2) => Math.abs(x2 - x1) < 2 && Math.abs(y2 - y1) < 2;
queries.forEach(([checkX, checkY]) => {
  const thisSquareIlluminated = lamp.some(([lampX, lampY]) => (
    !isAdjacent(checkX, checkY, lampX, lampY) && (
      lampX === checkX
      || lampY === checkY
      || Math.abs(lampX - checkX) === Math.abs(lampY - checkY)
    )
  ));
  console.log(thisSquareIlluminated ? 'LIGHT' : 'DARK');
});

我不建议预先构建发光的方 block ，因为这样，给定一个查询，您将不知 Prop 有照明的特定方 block 是否仅因相邻的灯而具有照明，至少在不迭代所有的情况下不会知道再次灯 - 最好在选择查询后迭代它们一次。

请注意，N = 8 输入不会在任何地方使用 - 这是一个转移注意力的行为，除非您还需要检查灯/查询是否也在板上的有效空间中。