Решение проблемы Queens Attack II в HackerRank
Это задача среднего уровня сложности, которую можно найти здесь.
Анализ проблемы
Как указано в задаче, мы должны найти количество позиций, на которых ферзь может атаковать. Учитывая, что на доске будет k препятствий.
Как ферзь может атаковать в восьми направлениях. Простая логика для решения этой проблемы состоит в том, чтобы найти номер позиции, где ферзь может атаковать в каждом направлении, а затем пересечь препятствия, если они лежат на пути ферзя, если это так, затем уменьшить количество позиций до этого препятствия на этом пути. И требуется сумма позиций по восьми направлениям.
Решение
Так как нам нужно запомнить расстояние, на котором ферзь может атаковать в восьми направлениях. Этого можно добиться, сохранив значение ячейки (i, j), до которой ферзь может атаковать, или дистанцировавшись от позиции ферзя до ячейки (i, j). Мы будем использовать массив размером 8, в котором будет храниться номер позиции в восьми различных направлениях, где ферзь может атаковать.
int dist [8];
Для простоты начнем с подсчета количества позиций, на которых ферзь может атаковать без препятствий. Если размер шахматной доски nxn, а позиция ферзя (r_q, c_q), то для оси x и положения оси Y
dist [0] = c_q -1; // -ve расстояние по оси x
dist [1] = n-r_q; // + ve расстояние по оси Y
dist [2] = n -c_q; // + ve расстояние по оси x
dist [3] = r_q -1; // -ve расстояние по оси Y
Для позиций с наклоном -1 или +1
dist [4] = min (dist [0], dist [1]); // минимум -ve оси x и + ve оси y
dist [5] = min (dist [1], dist [2]); // минимум + ve по оси x и + ve по оси y
dist [6] = min (dist [2], dist [3]); // минимум + ve x- ось и -ve ось y
dist [7] = min (dist [3], dist [0]); // минимум -ve оси x и -ve оси y
Теперь мы хотим перебрать препятствия и выяснить, находится ли оно на пути атаки ферзя. Для этого вычтем позицию ферзя из позиции препятствий.
int y = препятствия [k] [0] -r_q;
int x = препятствия [k] [1] -c_q;
На пути ферзя будут препятствия, если либо x, либо y равно нулю, либо , если наклон равен 1 или -1.
Затем мы просто обновим соответствующее значение пути, если оно ближе, чем предыдущая позиция препятствий или со стороны шахматной доски.
Полный код в cpp находится здесь
