在矩阵内部寻找内矩阵外层的算法

Question

我正在尝试解决以下算法，但卡住了。我希望你能帮忙。通过给出：大小为 N*N 的主矩阵大小为 K*L 的内矩阵（内矩阵包含在主矩阵中，索引已给出）。我应该编写一个函数，返回内部矩阵外层所有元素的列表。如果没有元素，则返回一个空列表。在每次迭代中，内层矩阵的大小越来越大，包括之前的内层矩阵+外层。例如：通过给定黑色主矩阵和红色内矩阵，返回黄色标记的元素。继续直到返回一个空列表。我被困在哪里通过增加内部矩阵的范围 +1 并比较主矩阵和内部矩阵的边缘，我可以轻松找到外层的元素。但是，我卡住了如何一般地增加循环（增加层数）。顺便说一句，我试图避免递归解决方案。

Answer 1

如果我正确理解了您的问题，您可以简单地分别跟踪内部矩阵 (y1, x1) 和 (y2, x2) 左上角和右下角的坐标。然后，您可以轻松获得外层并扩展内部矩阵，如下所示：

获取外层：这些元素的坐标是

• (y1-1, j) for j in max(0, x1-1),...,min(N-1, x2+1) （顶行，如果 y1 > 0）

• (y2+1, j) for j in max(0, x1-1),...,min(N-1, x2+1) （底行，如果 y2 < N-1）

• (i, x1-1) for i in y1,...,y2（左列，如果 x1 > 0）

• (i, x2+1) for i in y1,...,y2（右列，如果 x2 < N-1）

扩展内部矩阵：你只需要更新角坐标

• y1 = max(0, y1-1), x1 = max(0, x1-1)

• y2 = min(N-1, y2+1), x2 = min(N-1, x2+1)

然后重复，直到 (y1, x1) == (0, 0) 和 (y2, x2) == (N-1, N-1)