Соседи в матрице — алгоритм

#algorithm #matrix

#алгоритм #матрица

Вопрос:

У меня проблема с разработкой алгоритма для «графика»: (Может быть, кто-нибудь из вас будет так добр и направит меня как-нибудь <3

Задача заключается в следующем: у нас есть доска размером не менее 3×3 (она не обязательно должна быть квадратной, например, она может быть 4×5). Пользователь задает последовательность ходов (как в шаблоне блокировки Android). Задача состоит в том, чтобы проверить, сколько точек, которые он дал, соседствуют друг с другом по горизонтали или вертикали.

Вот пример: Матрица:

  • 1 2 3 4
  • 5 6 7 8
  • 9 10 11 12

Пользователь ввел код: 10,6,7,3 Алгоритм должен вернуть число 3, потому что:

  1. 10 является соседом 6
  2. 6 является соседом 7
  3. 7 является соседом 3

В конечном итоге вернет 3

Второй пример: матрица:

  • 1 2 3
  • 4 5 6
  • 7 8 9

Пользователь ввел код: 7,8,6,3

Алгоритм должен возвращать 2, потому что:

  1. 7 является соседом 8
  2. 8 не является соседом 6
  3. 6 является соседом 3

В конечном итоге возвращает 2 Ofc количество операций, равное длине массива — 1

Извините за «иль» и «тутай», я поляк

Комментарии:

1. Звучит как проблема с домашним заданием. Можете ли вы продемонстрировать, что вы действительно пытались сделать это первым?

2. @JIguadeza я добавил в качестве ссылки img

3. Могут ли значения в матрице быть не просто последовательностью чисел?

4. Нет, {1,2,3,4,5 … строки * столбцы}

Ответ №1:

Если все коды уникальны, используйте их в качестве ключей к словарю (с парами (строка / столбец) в качестве значений). Пройдите по 2-му элементу пользовательского ввода до конца, проверьте, является ли math.Abs(cur.row-prev.row) math.Abs(cur.col-prev.col)==1. Это не экономит пространство, но имеет дело с пользовательским вводом в линейной сложности.

Ответ №2:

Идея в том, что у вас есть 4 условия, по одному для каждого направления. Задана любая матрица формы n,m , состоящая из последовательности целых чисел, И задан любой элемент:

  1. Элемент слева или справа всегда будет or - 1 относиться к данному элементу.
  2. Элемент вверх или вниз всегда будет or - m относиться к данному элементу.

Итак, если abs(x-y) is 1 or m , то x и y являются соседями.

Я демонстрирую это на python.

 def get_neighbors(seq,matrix):
    
    #Conditions
    check = lambda x,y,m: np.abs(x-y)==1 or np.abs(x-y)==m
    
    #Pairs of sequences appended with m
    params = zip(seq, seq[1:], [matrix.shape[1]]*(len(seq)-1))
    
    neighbours = [check(*i) for i in params]
    count = sum(neighbours)
    return neighbours, count

seq = [7,8,6,3]
matrix = np.arange(1,10).reshape((3,3))
neighbours, count = get_neighbors(seq, matrix)

print('Matrix:')
print(matrix)
print('')
print('Sequence:', seq)
print('')
print('Count of neighbors:',count)
 
 Matrix:
[[ 1  2  3  4]
 [ 5  6  7  8]
 [ 9 10 11 12]]

Sequence: [10, 6, 7, 3]

Count of neighbors: 3
 

Другой пример —

 seq = [7,8,6,3]
matrix = np.arange(1,10).reshape((3,3))
neighbours, count = get_neighbors(seq, matrix)
 
 Matrix:
[[1 2 3]
 [4 5 6]
 [7 8 9]]

Sequence: [7, 8, 6, 3]

Count of neighbors: 2
 

Ответ №3:

Итак, ваш ввод — это ширина таблицы, высота таблицы и список чисел.

 W = 4, H = 3, list = [10,6,7,3]
 

Есть два шага:

  1. Преобразуйте список чисел в список координат строк / столбцов (от 1 до [1,1], от 5 до [2,1], от 12 до [3,4]).
  2. В новом списке координат найдите последовательные пары, у которых одна координата идентична, а другая имеет разницу в 1.

Оба шага довольно просты (циклы «для»). У вас есть проблемы с 1 или 2?

Комментарии:

1. Может быть, с первым циклом for

2. Итак, в каждой строке есть 4 значения. Числа 1,2,3,4 находятся в первой строке, 5,6,7,8 во второй и т.д. Поэтому просто разделите координату на 4, чтобы получить индекс строки. Например, 10/4 = 2,5, «две с половиной строки», поэтому он должен быть в третьей строке.