在网格（二维数组）上查找坐标

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

只是为了可视化 lamp 和查询，您可以根据需要使用 pixel art generator。

我首先创建一个辅助函数 isAdjacent 来检查两个点是否相邻。然后，遍历每个查询（目标方块），并检查是否有 lamp 照亮了目标。问题简化为检查：

lamp不相邻，且至少满足以下条件之一：
lamp 要么具有相同的 X 坐标，要么
相同的Y坐标，或者
它们在同一条对角线上，可以通过查看lamp和目标的X坐标之间的差异是否等于[=49之间的差异来检查=]的和目标的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');
});

我不建议事先构建发光的方块，因为那样的话，给定一个查询，您将不知道一个特定的发光方块是否仅由于相邻的 lamp 而具有照明，在至少不是没有再次遍历所有 lamps - 最好只遍历一次，在选择查询后。

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

Answer 2

由于我们现在不在接受采访，我决定让代码不紧凑，这样更容易理解。如果你愿意，你可以缩短它。我喜欢这类问题，所以我慢慢来。

我还更新了视觉网格。现在您可以看到网格状态的变化。

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

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

/* ==================== VISUAL GRID ==================== */

function arrayFlatten(array) {
    var result = [];
    array.forEach(function (item) {
        if (item instanceof Array) {
            result = result.concat(arrayFlatten(item));
        } else {
            result.push(item);
        }
    });
    return result;
}

function createGrid(lamps, queries) {
    var grid = document.createElement("table");
    grid.classList.add("grid");
    var gridSize = Math.max.apply(null, arrayFlatten([lamps, queries])) + 1;
    
    document.body.appendChild(grid);
    
    // create cells
    for (var i = 0; i < gridSize; i++) {
        var row = document.createElement("tr");
        for (var j = 0; j < gridSize; j++) {
            var cell = document.createElement("td");
            row.appendChild(cell);
        }
        grid.appendChild(row);
    }
    
    // add lamps
    lamps.forEach(lamp => grid.rows[lamp[1]].cells[lamp[0]].classList.add("lamp"));

    var illuminatedRows = Array.from(new Set(lamps.map(([lampX, lampY]) => lampY)));
    var illuminatedCols = Array.from(new Set(lamps.map(([lampX, lampY]) => lampX)));
    illuminatedRows.sort();
    illuminatedCols.sort();

    // add lights
    // horizontal
    for (var i = 0; i < grid.rows.length; i++) {
        if (illuminatedRows.includes(i)) {
            Array.from(grid.rows[i].cells).forEach(cell => cell.classList.add("horizontal-light"));
        }
    }
    // vertical
    for (var i = 0; i < grid.rows.length; i++) {
        for (var j = 0; j < grid.rows[i].cells.length; j++) {
            if (illuminatedCols.includes(j)) {
                grid.rows[i].cells[j].classList.add("vertical-light");
            }
        }
    }
    // diagonal
    for (var i = 0; i < grid.rows.length; i++) {
        for (var j = 0; j < grid.rows[i].cells.length; j++) {
            var x = j;
            var y = i;
            lamps.forEach(function (lamp) {
                if (isDiagonal(lamp[0], lamp[1], x, y)) {
                    grid.rows[i].cells[j].classList.add("diagonal-light");
                }
            });
        }
    }
    
}

createGrid(lamps, queries);

/* ==================== CALCULATION ==================== */

function isHorizontal(y1, y2) {
    return y1 == y2;
}

function isVertical(x1, x2) {
    return x1 == x2;
}

function isDiagonal(x1, y1, x2, y2) {
    return Math.abs(x1 - x2) == Math.abs(y1 - y2);
}

function isIlluminated(queryX, queryY, lampX, lampY) {
    return isHorizontal(queryY, lampY) || isVertical(queryX, lampX) || isDiagonal(queryX, queryY, lampX, lampY);
}

function isAdjacent(x1, y1, x2, y2) {
    return Math.abs(x2 - x1) < 2 && Math.abs(y2 - y1) < 2
}

// check every lamp for each query
function checkLamps(lamps, queryX, queryY) {
    // store checks for each lamp for a query
    var checks = [];
    // loop every lamp
    for (var i = lamps.length - 1; i >= 0; i--) {
        var lampX = lamps[i][0];
        var lampY = lamps[i][1];
        // check if the target cell is adjacent to the current lamp
        if (isAdjacent(queryX, queryY, lampX, lampY)) {
            console.log("Query (" + [queryX, queryY].join() + ") is adjacent to lamp (" + [lampX, lampY].join() + "). Removing this lamp.");
            // lamp is adjacent; remove it
            lamps.splice(i, 1);
            // create a grid with the new state (for visual purposes)
            createGrid(lamps, queries);
            // skip this lamp
            continue;
        } else {
            // storing the check for the current lamp
            checks.push(isIlluminated(queryX, queryY, lampX, lampY));
        }
    }
    // if all checks are false, it's dark
    // if there's even a single true, that means the cell is illuminated by a lamp
    if (checks.includes(true)) {
        console.log("(" + [queryX, queryY].join() + ") is LIGHT");
    } else {
        console.log("(" + [queryX, queryY].join() + ") is DARK");
    }
}

function checkLampIllumination(lamps, queries) {
    // create a local copy of lamps because it'll (might) mutate
    var lamps = lamps.slice();
    // loop queries
    queries.forEach(([queryX, queryY]) => checkLamps(lamps, queryX, queryY));
}

checkLampIllumination(lamps, queries);

.grid {
    background-color: black;
    border-collapse: collapse;
    margin-right: 1em;
    float: left;
}
.grid td {
    width: 25px;
    height: 25px;
    border: 1px solid hsl(0, 0%, 50%);
}
.grid td.horizontal-light,
.grid td.vertical-light,
.grid td.diagonal-light {
    background-color: hsla(0, 0%, 80%, .33);
}
.grid td.horizontal-light.vertical-light,
.grid td.horizontal-light.diagonal-light,
.grid td.vertical-light.diagonal-light {
    background-color: hsla(0, 0%, 80%, .45);
}
.grid td.horizontal-light.vertical-light.diagonal-light {
    background-color: hsla(0, 0%, 80%, .6);
}
.grid td.lamp {
    background-color: hsl(0, 0%, 100%) !important;
}

在网格（二维数组）上查找坐标

Finding coordinates on a grid (2D array)

javascript

arrays

matrix

depth-first-search

breadth-first-search