Нахождение элементов на расстоянии k от матрицы - PullRequest
Новая
       16

Нахождение элементов на расстоянии k от матрицы

1 голос
/ 16 мая 2011

Учитывая матрицу * n и значение k, как нам найти всех соседей для каждого элемента?например: в матрице 4*4 с k=2, скажем, матрица имеет вид: 

[ 1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15 16]

, где эти значения являются индексами местоположения, соседями для 1 are 1,2,3,5,6,9.Значения 3,6 and 9 приходят только потому, что k = 2, и их не было бы, если k было = 1.

аналогично соседям из 6 будет 1 2 3 5 6 7 8 9 10 11 and 14

Не могли бы вы помочь мне написатькод ac для реализации этого в c ++.

Это проблема соседства фон Неймана, пожалуйста, можете кто-нибудь реализовать его в c ++.Спасибо

Ответы [ 2 ]

1 голос
/ 16 мая 2011

Ваши соседи сформируют ромбовидный узор вокруг вашего целевого элемента.Точки алмаза будут в k прыжках от целевого элемента.Таким образом, верх будет на k рядов вверх, слева будет на k столбцов и т. Д. Алмаз расширяется равномерно при переходе от уровня к уровню.Если вы начинаете с верхней точки и идете на один ряд вниз (ближе к целевому узлу), то вы выходите по 1 на каждую сторону.Это симметрично в других направлениях.Другими словами, разница в координатах x между соседом и целевым узлом плюс разница в y будет <= k. </p>

Так что просто создайте два вложенных цикла for, которые итерируют по этому ромбу.Внешний цикл повторяется по строкам, внутренний цикл по столбцам.Начните сверху, затем увеличивайте ромб на 1 на каждой итерации внешнего цикла, пока не достигнете той же строки, что и целевой элемент, затем сжимайтесь, пока не достигнете нижней точки.Очевидно, вам нужно проверить граничные условия для выхода за пределы матрицы.

0 голосов
/ 16 мая 2011

Это должно сделать трюк для k = 1. Внесите незначительные изменения, чтобы он работал для всех k 

int width = 4;
int height = 4;
int k = 1;
int value = 2;

bool hasRight = (value % width != 0);
bool hasLeft = (value % width != 1);
bool hasTop = (value > 4);
bool hasBottom = (value < (height * width - width));

cout << value;  // Always itself
if(hasRight == true) {
 cout << value+1 << " ";  // Right
 if(hasTop == true) {
  cout << value-width << " " << value-width+1 << " "; // Top and Top-right
 }
 if(hasBottom == true) {
  cout << value+width << " " << value+width+1; // Bottom and Bottom-right
 }
}

if(hasLeft == true) {
 cout << value-1 << " ";  // Left
 if(hasTop == true) {
  cout << value-width-1 << " ";  // Top-left
 }
 if(hasBottom == true) {
  cout << value+width-1 << " ";  // Bottom-left
 }
}
...