Алгоритм для проверки всех смежных точек

#c #data-structures

#c #структуры данных

Вопрос:

Я пытаюсь найти наиболее эффективный способ обхода всех соседних ячеек в сетке.

Например, допустим, у меня есть 2D-массив, представленный в виде: vector <Item> grid;

и у меня есть точка в этой сетке (представленная синей ячейкой): grid[x][y];

и я хочу, чтобы он пересекал все смежные координаты.

Так, например, если бы моя точка была (1,1), она могла бы пройти (0,0) (0,1) (0,2) (1,0) (1,2) (2,0) (2,1) (2,2) каковы 8 точек, которые его окружают (исключая случай на данный момент, когда (x, y)находится в углу или на краю сетки).

Каков наилучший способ сделать это на C ? моей первоначальной мыслью было выполнить поиск в ширину, какие-нибудь мысли?

1. Я не уверен, что понимаю вопрос. Разве вы не можете просто перебирать структуру, по одному тайлу за раз, и для каждого тайла проверять его соседей с помощью 8 заданных вами смещений координат? Я не уверен, как входит BFS

2. В 2D-сетке не более 8 смежных ячеек. Почему вы беспокоитесь об эффективности для такого небольшого числа? Преждевременная оптимизация? Лучше было бы найти удобный способ обхода соседей.

3. Компьютеры действительно очень хороши в выполнении простых вещей очень и очень быстро. Вы получаете прирост производительности по сравнению с simple и stupid только тогда, когда smart устраняет необходимость выполнять работу, и даже тогда smart должен устранить достаточно работы, чтобы преодолеть преимущество в скорости, с которого начинается stupid. В этом случае, что бы вы ни делали, вам нужно посетить все 8 соседей (но следите за краями!), Поэтому вы не можете исключить какую-либо работу.

Ответ №1:

Вот один из способов перебора соседей:

 for (int i : {-1, 0, 1})
  for (int j : {-1, 0, 1}) 
    if (i amp;amp; j)
      std::cout << grid[x   i][y   j]; // prints all the neighbours

Убедитесь grid , что также учитываются края.

Это просто удобный способ перебора соседей. Не беспокойтесь об эффективности, если вы не измерили свой код и не обнаружили, что этот код является узким местом в производительности.

1. Кроме того, хороший компилятор оптимизирует Smurf из этих циклов. Вам действительно придется поработать над его улучшением.

2. спасибо за ваш ответ, это кажется лучшим способом, тем более, что операция max O (8)