Dada una array 2D queens[][] que consta de las coordenadas de N reinas en un tablero de ajedrez de 8 * 8 y una array king[] que denota las coordenadas del rey, la tarea es encontrar las reinas que atacan al rey.
Ejemplos:
Entrada: reinas[][] = {{0, 1}, {1, 0}, {4, 0}, {0, 4}, {3, 3}, {2, 4}}, rey[] = {2, 3}
Salida: {{0, 1}, {2, 4}, {3, 3}}Explicación: Las reinas en las coordenadas {0, 1} y {3, 3} están atacando diagonalmente al rey y la reina en {2, 4} está verticalmente debajo del rey.
Entrada: reinas[][]] = {{4, 1}, {1, 0}, {4, 0}}, rey[] = {0, 0}
Salida: {{1, 0}}
Enfoque Siga los pasos a continuación para resolver el problema:
- Iterar sobre la array queens[][] .
- Por cada coordenada atravesada, comprueba todas las posibilidades de atacar al rey, es decir, horizontal, vertical y diagonalmente. Si se descubre que está atacando al rey, verifique lo siguiente:
- Si ninguna otra reina está atacando al rey desde esa dirección, incluido el rey actual como atacante.
- Si ya hay un atacante presente en esa dirección, comprueba si la reina actual es el atacante más cercano o no. Si se determina que es cierto, incluye la reina del centavo como atacante. De lo contrario, proceda a las siguientes coordenadas.
- Finalmente, imprime todas las coordenadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the queen
// closest to king in an
// attacking position
int dis(vector<int> ans,
vector<int> attacker)
{
return abs(ans[0] - attacker[0])
+ abs(ans[1] - attacker[1]);
}
// Function to find all the queens
// attacking the king in the chessboard
vector<vector<int> > findQueens(
vector<vector<int> >& queens,
vector<int>& king)
{
vector<vector<int> > sol;
vector<vector<int> > attackers(8);
// Iterating over the coordinates
// of the queens
for (int i = 0; i < queens.size(); i++) {
// If king is horizontally on
// the right of current queen
if (king[0] == queens[i][0]
&& king[1] > queens[i][1]) {
// If no attacker is present
// in that direction
if ((attackers[3].size() == 0)
// Or if the current queen is
// closest in that direction
|| (dis(attackers[3], king)
> dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[3] = queens[i];
}
// If king is horizontally on
// the left of current queen
if (king[0] == queens[i][0]
&& king[1] < queens[i][1]) {
// If no attacker is present
// in that direction
if ((attackers[4].size() == 0)
// Or if the current queen is
// closest in that direction
|| (dis(attackers[4], king)
> dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[4] = queens[i];
}
// If the king is attacked by a
// queen from the left by a queen
// diagonal above
if (king[0] - queens[i][0]
== king[1] - queens[i][1]
&& king[0] > queens[i][0]) {
// If no attacker is present in
// that direction
if ((attackers[0].size() == 0)
// Or the current queen is
// the closest attacker in
// that direction
|| (dis(attackers[0], king)
> dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[0] = queens[i];
}
// If the king is attacked by a
// queen from the left by a queen
// diagonally below
if (king[0] - queens[i][0]
== king[1] - queens[i][1]
&& king[0] < queens[i][0]) {
// If no attacker is present in
// that direction
if ((attackers[7].size() == 0)
// Or the current queen is
// the closest attacker in
// that direction
|| (dis(attackers[7], king)
> dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[7] = queens[i];
}
// If the king is attacked by a
// queen from the right by a queen
// diagonally above
if (king[1] - queens[i][1] == 0
&& king[0] > queens[i][0]) {
// If no attacker is present in
// that direction
if ((attackers[1].size() == 0)
// Or the current queen is
// the closest attacker in
// that direction
|| (dis(attackers[1], king)
> dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[1] = queens[i];
}
// If the king is attacked by a
// queen from the right by a queen
// diagonally below
if (king[1] - queens[i][1] == 0
&& king[0] < queens[i][0]) {
// If no attacker is present in
// that direction
if ((attackers[6].size() == 0)
// Or the current queen is
// the closest attacker in
// that direction
|| (dis(attackers[6], king)
> dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[6] = queens[i];
}
// If a king is vertically below
// the current queen
if (king[0] - queens[i][0]
== -(king[1] - queens[i][1])
&& king[0] > queens[i][0]) {
// If no attacker is present in
// that direction
if ((attackers[2].size() == 0)
// Or the current queen is
// the closest attacker in
// that direction
|| (dis(attackers[2], king)
> dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[2] = queens[i];
}
// If a king is vertically above
// the current queen
if (king[0] - queens[i][0]
== -(king[1] - queens[i][1])
&& king[0] < queens[i][0]) {
// If no attacker is present in
// that direction
if ((attackers[5].size() == 0)
// Or the current queen is
// the closest attacker in
// that direction
|| (dis(attackers[5], king)
> dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[5] = queens[i];
}
}
for (int i = 0; i < 8; i++)
if (attackers[i].size())
sol.push_back(attackers[i]);
// Return the coordinates
return sol;
}
// Print all the coordinates of the
// queens attacking the king
void print(vector<vector<int> > ans)
{
for (int i = 0; i < ans.size();
i++) {
for (int j = 0; j < 2; j++)
cout << ans[i][j] << " ";
cout << "\n";
}
}
// Driver Code
int main()
{
vector<int> king = { 2, 3 };
vector<vector<int> > queens
= { { 0, 1 }, { 1, 0 },
{ 4, 0 }, { 0, 4 },
{ 3, 3 }, { 2, 4 } };
vector<vector<int> > ans
= findQueens(queens, king);
print(ans);
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
class GFG{
// Method to find the queen closest
// to king in an attacking position
private static int dis(int[] ans, int[] attacker)
{
return Math.abs(ans[0] - attacker[0]) +
Math.abs(ans[1] - attacker[1]);
}
// Method to find all the queens
// attacking the king in the chessboard
private static List<List<Integer>> findQueens(
int[][] queens, int[] king)
{
List<List<Integer>> sol = new ArrayList<List<Integer>>();
int[][] attackers = new int[8][2];
for(int i = 0; i < 8; i++)
{
Arrays.fill(attackers[i], -1);
}
for(int i = 0; i < queens.length; i++)
{
// If king is horizontally on
// the right of current queen
if (king[0] == queens[i][0] &&
king[1] > queens[i][1])
{
// If no attacker is present
// in that direction
if ((attackers[3][0] == -1) ||
// Or if the current queen is
// closest in that direction
(dis(attackers[3], king) >
dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[3] = queens[i];
}
// If king is horizontally on
// the left of current queen
if (king[0] == queens[i][0] &&
king[1] < queens[i][1])
{
// If no attacker is present
// in that direction
if ((attackers[4][0] == -1) ||
// Or if the current queen is
// closest in that direction
(dis(attackers[4], king) >
dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[4] = queens[i];
}
// If the king is attacked by a
// queen from the left by a queen
// diagonal above
if (king[0] - queens[i][0] ==
king[1] - queens[i][1] &&
king[0] > queens[i][0])
{
// If no attacker is present in
// that direction
if ((attackers[0][0] == -1) ||
// Or the current queen is
// the closest attacker in
// that direction
(dis(attackers[0], king) >
dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[0] = queens[i];
}
// If the king is attacked by a
// queen from the left by a queen
// diagonally below
if (king[0] - queens[i][0] ==
king[1] - queens[i][1] &&
king[0] < queens[i][0])
{
// If no attacker is present in
// that direction
if ((attackers[7][0] == -1) ||
// Or the current queen is
// the closest attacker in
// that direction
(dis(attackers[7], king) >
dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[7] = queens[i];
}
// If the king is attacked by a
// queen from the right by a queen
// diagonally above
if (king[1] - queens[i][1] == 0 &&
king[0] > queens[i][0])
{
// If no attacker is present in
// that direction
if ((attackers[1][0] == -1) ||
// Or the current queen is
// the closest attacker in
// that direction
(dis(attackers[1], king) >
dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[1] = queens[i];
}
// If the king is attacked by a
// queen from the right by a queen
// diagonally below
if (king[1] - queens[i][1] == 0 &&
king[0] < queens[i][0])
{
// If no attacker is present in
// that direction
if ((attackers[6][0] == -1) ||
// Or the current queen is
// the closest attacker in
// that direction
(dis(attackers[6], king) >
dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[6] = queens[i];
}
// If a king is vertically below
// the current queen
if (king[0] - queens[i][0] ==
-(king[1] - queens[i][1]) &&
king[0] > queens[i][0])
{
// If no attacker is present in
// that direction
if ((attackers[2][0] == -1) ||
// Or the current queen is
// the closest attacker in
// that direction
(dis(attackers[2], king) >
dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[2] = queens[i];
}
// If a king is vertically above
// the current queen
if (king[0] - queens[i][0] ==
-(king[1] - queens[i][1]) &&
king[0] < queens[i][0])
{
// If no attacker is present in
// that direction
if ((attackers[5][0] == -1) ||
// Or the current queen is
// the closest attacker in
// that direction
(dis(attackers[5], king) >
dis(queens[i], king)))
// Set current queen as
// the attacker
attackers[5] = queens[i];
}
}
for(int i = 0; i < 8; i++)
if (attackers[i][0] != -1)
sol.add(
Arrays.stream(
attackers[i]).boxed().collect(
Collectors.toList()));
// Return the coordinates
return sol;
}
// Print all the coordinates of the
// queens attacking the king
private static void print(List<List<Integer>> ans)
{
for(int i = 0; i < ans.size(); i++)
{
for(int j = 0; j < 2; j++)
System.out.print(ans.get(i).get(j) + " ");
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
int[] king = { 2, 3 };
int[][] queens = { { 0, 1 }, { 1, 0 },
{ 4, 0 }, { 0, 4 },
{ 3, 3 }, { 2, 4 } };
List<List<Integer>> ans = findQueens(queens, king);
print(ans);
}
}
// This code is contributed by jithin
Python3
# Python3 program to implement # the above approach # Function to find the queen # closest to king in an # attacking position def dis(ans, attacker): return (abs(ans[0] - attacker[0]) + abs(ans[1] - attacker[1])) # Function to find all the # queens attacking the king # in the chessboard def findQueens(queens, king): sol = [] attackers = [[0 for x in range(8)] for y in range(8)] # Iterating over the coordinates # of the queens for i in range(len(queens)): # If king is horizontally on # the right of current queen if (king[0] == queens[i][0] and king[1] > queens[i][1]): # If no attacker is present # in that direction if ((len(attackers[3]) == 0) # Or if the current queen is # closest in that direction or ((dis(attackers[3], king) > dis(queens[i], king)))): # Set current queen as # the attacker attackers[3] = queens[i]; # If king is horizontally on # the left of current queen if (king[0] == queens[i][0] and king[1] < queens[i][1]): # If no attacker is present # in that direction if ((len(attackers[4]) == 0) # Or if the current queen is # closest in that direction or (dis(attackers[4], king) > dis(queens[i], king))): # Set current queen as # the attacker attackers[4] = queens[i]; # If the king is attacked by a # queen from the left by a queen # diagonal above if (king[0] - queens[i][0] == king[1] - queens[i][1] and king[0] > queens[i][0]): # If no attacker is present in # that direction if ((len(attackers[0]) == 0) # Or the current queen is # the closest attacker in # that direction or (dis(attackers[0], king) > dis(queens[i], king))): # Set current queen as # the attacker attackers[0] = queens[i] # If the king is attacked by a # queen from the left by a queen # diagonally below if (king[0] - queens[i][0] == king[1] - queens[i][1] and king[0] < queens[i][0]): # If no attacker is present in # that direction if ((len(attackers[7]) == 0) # Or the current queen is # the closest attacker in # that direction or (dis(attackers[7], king) > dis(queens[i], king))): # Set current queen as # the attacker attackers[7] = queens[i] # If the king is attacked by a # queen from the right by a queen # diagonally above if (king[1] - queens[i][1] == 0 and king[0] > queens[i][0]): # If no attacker is present in # that direction if ((len(attackers[1]) == 0) # Or the current queen is # the closest attacker in # that direction or (dis(attackers[1], king) > dis(queens[i], king))): # Set current queen as # the attacker attackers[1] = queens[i] # If the king is attacked by a # queen from the right by a queen # diagonally below if (king[1] - queens[i][1] == 0 and king[0] < queens[i][0]): # If no attacker is present in # that direction if ((len(attackers[6]) == 0) # Or the current queen is # the closest attacker in # that direction or (dis(attackers[6], king) > dis(queens[i], king))): # Set current queen as # the attacker attackers[6] = queens[i]; # If a king is vertically below # the current queen if (king[0] - queens[i][0] == -(king[1] - queens[i][1]) and king[0] > queens[i][0]): # If no attacker is present in # that direction if ((len(attackers[2]) == 0) # Or the current queen is # the closest attacker in # that direction or (dis(attackers[2], king) > dis(queens[i], king))): # Set current queen as # the attacker attackers[2] = queens[i] # If a king is vertically above # the current queen if (king[0] - queens[i][0] == -(king[1] - queens[i][1]) and king[0] < queens[i][0]): # If no attacker is present in # that direction if ((len(attackers[5]) == 0) # Or the current queen is # the closest attacker in # that direction or (dis(attackers[5], king) > dis(queens[i], king))): # Set current queen as # the attacker attackers[5] = queens[i] for i in range(8): f = 1 for x in attackers[i]: if x != 0: f = 0 break if f == 0: sol.append(attackers[i]) # Return the coordinates return sol # Print all the coordinates of the # queens attacking the king def print_board(ans): for i in range(len(ans)): for j in range(2): print(ans[i][j], end = " ") print() # Driver Code if __name__ == "__main__": king = [2, 3] queens = [[0, 1], [1, 0], [4, 0], [0, 4], [3, 3], [2, 4]] ans = findQueens(queens, king); print_board(ans); # This code is contributed by Chitranayal
Producción:
0 1 2 4 3 3
Complejidad temporal: O(N), donde N es el número de reinas
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA