Блог

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

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

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

Идея в том, что у вас есть 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
 

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

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

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

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

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