Найти положение ферзя на шахматной доске по заданным линиям атаки ферзя
Дана матричная матрица N × N [][] из N строк и N столбцов. На шахматной доске ровно один ферзь, и клетка, находящаяся под атакой ферзя, обозначается «Q» , а клетка, которая не подвергается атаке ферзя, обозначается «.». . Задача состоит в том, чтобы найти положение ферзя.
Примечание. Если позиция не может быть найдена, выведите пару -1 .
Примеры:
Input: {{‘Q’, ‘ Q’, Q’}, {‘Q’, Q’, Q’}, {‘Q’, Q’, Q’}}
Output: 2 2
Explanation: Queen is at the middle of the matrix, because,
it’s the only place from where you can attack in every cell
of the matrix of dimension 33.Input: {{Q, Q}, {Q, Q}}
Output: -1 -1
Explanation: Queen can be in any of the four positions.
Подход: Задача может быть решена на основе следующего наблюдения:
- Если N = 1, ферзь может быть только на [1, 1]
- Если N = 2, невозможно найти положение ферзя.
- Если N = 3, это частный случай.
- Проверяем, если каждая клетка находится под атакой ферзя, то она находится в [2, 2].
- В противном случае используйте вложенный цикл, чтобы пройти через каждую ячейку сетки и найти положение ферзя, проверяя 4 угла, 4 края и 1 среднее где-то условия одно за другим.
- Для N > 3 также используйте 2-й метод, как и для N = 3.
- Если цикл завершается и ничего не возвращается, то либо ферзя нет, либо ферзя найти невозможно, поэтому возвращаем -1, -1.
Ниже приведена реализация вышеуказанного подхода.
Временная сложность: O(N*N)
Вспомогательное пространство: O(1)