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 ，因为那样的话，给定一个查询，你不会知道一个特定的有照明的方 block 是否只有相邻灯的照明，至少在没有遍历所有的情况下是这样再次选择灯 - 最好在选择查询后迭代一次。

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