2次元配列内の要素の隣接要素(つまり、要素の周囲の8つの要素)を見つける簡単な方法はありますか?次のように、さまざまな組み合わせでインデックスを減算および加算するだけでは不十分です。
array[i-1][i]
array[i-1][i-1]
array[i][i-1]
array[i+1][i]
... 等々。
2次元配列内の要素の隣接要素(つまり、要素の周囲の8つの要素)を見つける簡単な方法はありますか?次のように、さまざまな組み合わせでインデックスを減算および加算するだけでは不十分です。
array[i-1][i]
array[i-1][i-1]
array[i][i-1]
array[i+1][i]
... 等々。
(擬似コード)
row_limit = count(array);
if(row_limit > 0){
column_limit = count(array[0]);
for(x = max(0, i-1); x <= min(i+1, row_limit); x++){
for(y = max(0, j-1); y <= min(j+1, column_limit); y++){
if(x != i || y != j){
print array[x][y];
}
}
}
}
もちろん、これには元のハードコードされたソリューションとほぼ同じ数の行が必要ですが、これを使用すると、「近隣」を可能な限り拡張できます(2〜3セル以上離れた場所)。
ベンのアプローチは正しいと思いますが、局所性を改善するために並べ替えるかもしれません。
array[i-1][j-1]
array[i-1][j]
array[i-1][j+1]
array[i][j-1]
array[i][j+1]
array[i+1][j-1]
array[i+1][j]
array[i+1][j+1]
境界チェックの問題を回避する 1 つのトリックは、配列の次元を必要以上に 2 大きくすることです。だから、このような小さなマトリックス
3 1 4
1 5 9
2 6 5
実際には次のように実装されています
0 0 0 0 0
0 3 1 4 0
0 1 5 9 0
0 2 6 5 0
0 0 0 0 0
次に、合計中に、両方の次元で 1 から 3 までの添字を付けることができます。上記の配列参照は有効であることが保証されており、最終的な合計には影響しません。この例では、c とゼロベースの添字を想定しています
以下は、@seb オリジナルの疑似コードからの実際の Javascript の例です。
function findingNeighbors(myArray, i, j) {
var rowLimit = myArray.length-1;
var columnLimit = myArray[0].length-1;
for(var x = Math.max(0, i-1); x <= Math.min(i+1, rowLimit); x++) {
for(var y = Math.max(0, j-1); y <= Math.min(j+1, columnLimit); y++) {
if(x !== i || y !== j) {
console.log(myArray[x][y]);
}
}
}
}
言語がこれをサポートしている場合、@SebaGR の代替:
var deltas = { {x=-1, y=-1}, {x=0, y=-1}, {x=1, y=-1},
{x=-1, y=0}, {x=1, y=0},
{x=-1, y=1}, {x=0, y=1}, {x=1, y=1} };
foreach (var delta in deltas)
{
if (x+delta.x < 0 || x + delta.x >= array.GetLength(0) ||
y+delta.y < 0 || y + delta.y >= array.GetLength(1))
continue;
Console.WriteLine("{0}", array[x + delta.x, y + delta.y]);
}
デルタを静的に割り当てることができれば、可読性、可能なパフォーマンスがわずかに向上します。
の隣人を印刷するにはL[row][column]
:
print(L[row-1][column-1], L[row-1][column], L[row-1][column+1])
print(L[row][column-1], L[row][column], L[row][column+1])
print(L[row+1][column-1], L[row+1][column], L[row+1][column+1])
これはおそらく、可能なネイバーを印刷するのが最も速く/最も簡単な方法です。ただし、インデックスの境界外チェックを必ず実行してください。
一部の言語はこれを行うためのショートカット方法を提供するかもしれませんが、私は何も知りません。
私が通常取っているアプローチは、このブログの下部に記載されています: https://royvanrijn.com/blog/2019/01/longest-path/
方向をハードコーディングしたり、2 つのネストされたループを作成したりする代わりに、8 つの「方向」に単一の整数ループを使用し、(i % 3)-1 と (i / 3)-1; を使用します。画像付きのブログをチェックしてください。
それほど深くネストせず、簡単に記述でき、多くのコードは必要ありません!
多くはあなたのデータが何であるかに依存します。たとえば、2D配列が論理行列の場合、行を整数に変換し、ビット演算を使用して必要なものを見つけることができます。
より汎用的なソリューションについては、SebaGRのソリューションのように、インデックス作成に固執していると思います。
リスト内包表記のネストされた for ループは少し醜いですが、これは短くなります:
def neighbours(m, i, j):
return [m[x][y] for x in [i-1,i,i+1] for y in [j-1,j,j+1] if x in range(0,len(m)) and y in range(0,len(m[x])) and (x,y) != (i,j)]
行と列は、行と列の合計数です
CellIndex 構造体またはクラスを定義します。または、インデックスの代わりに実際の値を返すこともできます。
public List<CellIndex> GetNeighbors(int rowIndex, int colIndex)
{
var rowIndexes = (new int[] { rowIndex - 1, rowIndex, rowIndex + 1 }).Where(n => n >= 0 && n < Rows);
var colIndexes = (new int[] { colIndex - 1, colIndex, colIndex + 1 }).Where(n => n >= 0 && n < Cols);
return (from row in rowIndexes from col in colIndexes where row != rowIndex || col != colIndex select new CellIndex { Row = row, Col = col }).ToList();
}
private ArrayList<Element> getNeighbors(Element p) {
ArrayList<Element> n = new ArrayList<Element>();
for (int dr = -1; dr <= +1; dr++) {
for (int dc = -1; dc <= +1; dc++) {
int r = p.row + dr;
int c = p.col + dc;
if ((r >= 0) && (r < ROWS) && (c >= 0) && (c < COLS)) {
// skip p
if ((dr != 0) || (dc != 0))
n.add(new Element(r, c));
}
}
}
return n;
}
C# のコードは次のとおりです。
public Cell[,] MeetNeigbours(Cell[,] Grid)
{
for (int X = 0; X < Grid.GetLength(0); X++)
{
for (int Y = 0; Y < Grid.GetLength(1); Y++)
{
int NeighbourCount = 0;
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
if (CellExists(Grid, (X + i)), (Y + j) && (i != 0 && j != 0))
{
Grid[X, Y].Neighbours[NeighbourCount] = Grid[(X + i), (Y + j)];
}
if(!(i == 0 && j == 0))
{
NeighbourCount++;
}
}
}
}
}
return Grid;
}
public bool CellExists(Cell[,] Grid, int X, int Y)
{
bool returnValue = false;
if (X >= 0 && Y >= 0)
{
if (X < Grid.GetLength(0) && Y < Grid.GetLength(1))
{
returnValue = true;
}
}
return returnValue;
}
「Cell」クラスは次のようになります。
public class Cell
{
public Cell()
{
Neighbours = new Cell[8];
}
/// <summary>
/// 0 3 5
/// 1 X 6
/// 2 4 7
/// </summary>
public Cell[] Neighbours;
}