Итак, вы должны проверить, есть ли столкновение.Для того, чтобы произошло столкновение, если я понимаю ваш пример, после того, как автомобили движутся, в одном и том же месте должны быть две машины.
Я думаю, что мы можем использовать здесь концепцию пятна или положения.Вы можете сохранить позиции, на которых в данный момент есть автомобиль, в наборе (координаты матрицы или любой другой объект, который лучше всего подходит для вашей задачи).Когда автомобиль движется, удалите его позицию из набора и вставьте новую в набор.
После того, как мы это сделаем, вам нужно будет только проверить, содержит ли набор следующую позицию автомобиля, чтобы узнать, будет ли столкновение или нет, и в консультации HashSet, которая является O (1).Примените это к количеству автомобилей (n), и вы будете управлять коллизиями в O (n).
Пример для дальнейшего уточнения:
Выэта матрица позиций с автомобилями на «О» и пустыми пространствами на «Х».Это означает, что у вас будет машина на позиции 1, а другая - на позиции 8, если вы пронумеруете свои позиции из верхнего левого угла.
O X X
X X X
X O X
Это будет означать, что у вас есть набор целых чисел с позициями 1 и8 на это.Теперь, пример для перемещения одного из автомобилей:
Автомобиль в положении 1 перемещается в положение 2: Вы проверяете, находится ли положение 2 в наборе [O (1)].Это не так.Вы удаляете позицию 1 из набора [O (1)] и добавляете позицию 2 к набору [O (1)], потому что теперь в позиции 1 нет машины, а в позиции 2.
Повторите для каждого автомобиля (n) => O (1) * O (n) = O (n).