Метод поиска объектов

Question

Я знаю, что это не интересная тема для вас, но я просто практикую немного C++. Какой метод я могу использовать, чтобы узнать, сколько объектов можно увидеть из точки. ОК, так вот пример:

# # * # * 
# * # * # 
* # P * * 
# # # # # 
* # * # * 

так, то P является точкой, в которой вы должны сказать, сколько момент вы можете увидеть, # пустые пространства и * являются объектами. я думаю, что я могу использовать такой алгоритм Ли и где объект останавливает счетчик ..

я сделал матрицу

f>>N>>M; 
for (i=1;i<=N;i++) 
{ 
    for (j=1;j<=M;j++) 
    { 
    f>>l; 
    switch (l) 
     { 
     case '#': { a[i][j]=0; break;} 
     case '*': { a[i][j]=-2; break;} 
     case 'P': { a[i][j]=-1; break;} 
     } 
    } 
} 

и теперь, когда счетчик достигает -2 остановки .. пожалуйста, помогите мне : а3

Answer 1

Все, что я могу сказать от того, что вы показываете выглядит следующим образом:

я сделал матрицу

предположит, что вы означали иметь что-то вроде

f>>N>>M; 

int a[N][M]; // Note this is non standard! 

инициализации ваших для петель неправильно:

for (i=1 /* <---- */ ;i<=N;i++) 

массива индексов в C++ начинаются с 0, вашей инициализация цикла должна выглядеть следующим образом:

for (i=0 /* Note the 0 */ ;i<=N;i++) 

Answer 2

Основной пункт здесь - проверка видимости. Определенная точка (x, y) видна (px, py), если на линии нет объектов (px, py) - (x, y). Объекты могут находиться только на целочисленных позициях. Поэтому мы должны проверять каждую точку, лежащую на этой линии.

.................. 
.    o 
.    x 
.   x 
.  x  
. x 
. p 

Предположим, что мы хотим, чтобы проверить видимость o от p. Сначала мы должны вычислить разницу. В этом случае o - dx=15 единиц права и dy=5 единиц, превышающих p. Объекты могут находиться только на определенных позициях. Возможные положения распределяются по линии с равным расстоянием. Количество точек определяется наибольшим общим делителем dx и dy (поскольку оба значенияи dy должны быть целыми числами). Gcd 5 и 15 - 5. Таким образом, мы должны проверить 5 возможных позиций (помечены x). stepX = dx/gcd = 15/5 = 3 и stepY = dy/gcd = 5/5 = 1. Последний пункт - o, поэтому нам не нужно это проверять.

Мы можем определить функцию для проверки видимости, что делает что-то вроде следующего (в предположении, что существует gcd функция):

bool isVisible(int** matrix /*or any other appropriate declaration */, int px, int py, int ox, int oy) 
{ 
    int dx = ox - px; 
    int dy = oy - py; 
    int div = gcd(abs(dx), abs(dy)); 
    int stepX = dx/div; 
    int stepY = dy/div; 
    for(int i = 1; i < div; ++i) 
    { 
     int checkX = px + i * stepX; //these could be computed incrementally 
     int checkY = py + i * stepY; 
     if (matrix[checkX][checkY] == 2) //blocked 
      return false; 
    } 
    return true; 
} 

Обратите внимание, что эта функция является иллюстрацией и не может быть функциональным.

Если вы построили матрицу и знаете координаты p, тогда вам нужно только перебрать каждую позицию. Вызовите вышеуказанную функцию с положением, чтобы проверить, видно ли это и увеличивать счетчик, если это так. Пропустите p в процессе.

Вот еще один пример, когда более очевидно, что требуется gcd. dx = 16, dy = 12

.................. 
.    o 
.     
. 
.   x 
. 
. 
.  x 
. 
. 
. x 
. 
. 
.p