Find neighboring elements in a 2D matrix

Question

I have a 2-dimensional matrix of order m * n

00 01 02 03 ....0n 10 11 12 13 ....1n 20 21 22 23 ....2n .. m0 m1 m2 m3 ...mn 

From this, given the element, I need to write a method that returns its adjacent elements. Adjacent elements are located horizontally, vertically or diagonally.

For example, adjacent element 01 is equal to 00.02, 10.11, 11.12 adjacent element 00 is equal to 01, 10.11 adjacent element of 11 is equal to 00.01.02, 10.12, 12.21, 22

Can someone help me with an optimistic algorithm to solve this problem?

Answer 1

 public static IEnumerable<T> AdjacentElements<T>(T[,] arr, int row, int column) { int rows = arr.GetLength(0); int columns = arr.GetLength(1); for (int j = row - 1; j <= row + 1; j++) for (int i = column - 1; i <= column + 1; i++) if (i >= 0 && j >= 0 && i < columns && j < rows && !(j == row && i == column)) yield return arr[j, i]; } ... var arr = new[,] { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} }; var results = AdjacentElements(arr, 1, 3); foreach(var result in results) Console.WriteLine(result) 

This gives the answer: 3 4 7 11 12 (elements adjacent to 8).

Answer 2

It seems that the elements in the 2d array (be [n] [m]) grow horizontally and vertically. Therefore, for this question, we need to first find the index of the element. Therefore, if we can find the element faster, we can optimize the solution. The question is how do we find it in an effective way. One approach is to take the middle element of the matrix and check this element with it

if this element is smaller than the middle element, then our solution lies in the matrix a [0] [0] on [n / 2] [m / 2], since all the elements on the right and bottom are larger than the average (since this element is smaller than the middle element), therefore, we reduced our search space from [n] [m] to [n / 2] [m / 2], which is one quarter of the original size.

if this element is larger than the middle element, then our solution does not lie in the matrices a [0] [0] to [n / 2] [m / 2], because all the elements on the left and on the top are smaller than the average (since this element is larger than the middle element ), so our search space is a full array minus [0] [0] by [n / 2] [m / 2], which is three-quarters of the original size. A common array minus a [0] [0] to [n / 2] [m / 2] means there will be three recursive calls with the index of the array

  --------->a[0][m/2](start index) to a[n/2][m](end index) --------->a[n/2][0](start index) to a[n][m/2](end index) --------->a[n/2][m/2](start index) to a[n][m](end index) 

Now recursively call the same function as in our search space.

The time complexity of our function will be next. NOTE:. The time function n represents the total number of elements, but not the number of rows, as indicated. n = (no_of_rows) * (no_of_columns)

  _________________T(n/4) if given element is less than middle of the array. / / T(n)==========------------------- 1 if n=1 (if element found) \ \_________________3T(n/4) if given element is greater than middle element of array 

so the timeout function will be

T (n) = 3T (n / 4) or T (n) = T (n / 4)

 In worst case T(n)=3T(n/4) T(n)=3{3T(n/4)} T(n)=3power(i)T(n/(4)poweri) equation------> (1) 

But T (1) = 1 (guessing the given element is found in the array)

 so n/(4power(i))=1 ====> n=2power(2*i) ====> n=2power(2*i) 

Talking log with base 2 on both sides (log[n])/2=i ====> i = log (sqrt (n))

substituting equation 1, we obtain T (n) = 3power (log [sqrt (n)])

So, after finding the element using the index, we can find its neighbors. Let's say the item is found in [i] [j], then type

  { a[i-1][j-1], a[i-1][j], a[i-1][j+1], a[i][j-1], a[i][j+1], a[i+1][j-1], a[i+1][j], a[i+1][j+1] } 

on condition,

  0<i<n and 0<j<n . 

Answer 3

Suppose you have a matrix string [n,m] , you can get the result by smoothing the matrix, the code example below:

 var array = matrix.Cast<string>() .ToList(); var index = array.IndexOf(input); var indexList = new List<int>() { index - n - 1, index - n, index - n + 1, index - 1, index + 1, index + n - 1, index + n , index + n + 1}; var result = array.Where((item, i) => indexList.Contains(i));