Given a 2D array queens[][] consisting of coordinates of N queens in an 8 * 8 chessboard and an array king[] denoting the coordinates of the king, the task is to find the queens that are attacking the king
Examples:
Input: queens[][] = {{0, 1}, {1, 0}, {4, 0}, {0, 4}, {3, 3}, {2, 4}}, king[] = {2, 3}
Output: {{0, 1}, {2, 4}, {3, 3}}Explanation:The queens at coordinates {0, 1} and {3, 3} are diagonally attacking the king and the queen at {2, 4} is vertically below the king.
Input: queens[][]] = {{4, 1}, {1, 0}, {4, 0}}, king[] = {0, 0}
Output : {{1, 0}}
Approach Follow the steps below to solve the problem:
- Iterate over the array queens[][].
- For every coordinate traversed, check for all possibilities of attacking the king, i.e. horizontally, vertically and diagonally. If found to be attacking the king, check for the following:
- If no other queen is attacking the king from that direction, including the current king as an attacker.
- If an attacker is already present in that direction, check if the current queen is the closest attacker or not. If found to be true, including the cent queen as an attacker. Otherwise, proceed to the next coordinates.
- Finally, print all the coordinates.
Below is the implementation of the above approach:
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 positionint 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 chessboardvector<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 // diagonally 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 kingvoid 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 Codeint 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 approachimport java.io.*;import java.util.*;import java.util.stream.Collectors;class GFG{// Method to find the queen closest// to king in an attacking positionprivate 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 chessboardprivate 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 // diagonally 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 kingprivate 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 Codepublic 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 positiondef 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 chessboarddef 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 # diagonally 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 kingdef print_board(ans): for i in range(len(ans)): for j in range(2): print(ans[i][j], end = " ") print()# Driver Codeif __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 |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;using System.Linq;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<int> > findQueens(int[][] queens, int[] king) { List<List<int> > sol = new List<List<int> >(); int[][] attackers = new int[8][]; for (int i = 0; i < 8; i++) { attackers[i] = new int[] { -1, -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) || (dis(attackers[3], king) > dis(queens[i], king))) 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) || (dis(attackers[4], king) > dis(queens[i], king))) attackers[4] = queens[i]; } if (king[0] - queens[i][0] == king[1] - queens[i][1] && king[0] > queens[i][0]) { if ((attackers[0][0] == -1) || (dis(attackers[0], king) > dis(queens[i], king))) attackers[0] = queens[i]; } if (king[0] - queens[i][0] == king[1] - queens[i][1] && king[0] < queens[i][0]) { if ((attackers[7][0] == -1) || (dis(attackers[7], king) > dis(queens[i], king))) attackers[7] = queens[i]; } if (king[1] - queens[i][1] == 0 && king[0] > queens[i][0]) { if ((attackers[1][0] == -1) || (dis(attackers[1], king) > dis(queens[i], king))) attackers[1] = queens[i]; } if (king[1] - queens[i][1] == 0 && king[0] < queens[i][0]) { if ((attackers[6][0] == -1) || (dis(attackers[6], king) > dis(queens[i], king))) attackers[6] = queens[i]; } if (king[0] - queens[i][0] == -(king[1] - queens[i][1]) && king[0] > queens[i][0]) { if ((attackers[2][0] == -1) || (dis(attackers[2], king) > dis(queens[i], king))) attackers[2] = queens[i]; } if (king[0] - queens[i][0] == -(king[1] - queens[i][1]) && king[0] < queens[i][0]) { if ((attackers[5][0] == -1) || (dis(attackers[5], king) > dis(queens[i], king))) attackers[5] = queens[i]; } } // Print all the coordinates of the// queens attacking the king for (int i = 0; i < 8; i++) { if (attackers[i][0] != -1) { List<int> temp = new List<int>(); temp.Add(attackers[i][0]); temp.Add(attackers[i][1]); sol.Add(temp); } }//Return the coordinates return sol; }//Driver code public static void Main() { int[][] queens = new int[6][]; queens[0] = new int[] { 0, 1 }; queens[1] = new int[] { 1, 0 }; queens[2] = new int[] { 4, 0 }; queens[3] = new int[] { 0, 4 }; queens[4] = new int[] { 3, 3 }; queens[5] = new int[] { 2, 4 }; int[] king = new int[] { 2, 3 }; List<List<int> > res = findQueens(queens, king); foreach(List<int> l in res) { Console.WriteLine("(" + l[0] + ", " + l[1] + ")"); } }} |
Javascript
// JavaScript program to implement// the above approach// Method to find the queen closest// to king in an attacking positionfunction dis(ans, 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 chessboardfunction findQueens(queens, king) { let sol = []; let attackers = Array.from({ length: 8 }, () => Array(8).fill(0)); for (let 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 // Or if the current queen is // closest in that direction if (attackers[3].length === 0 || 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 // Or if the current queen is // closest in that direction if (attackers[4].length === 0 || 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 // diagonally 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 // Or the current queen is // the closest attacker in // that direction if (attackers[0].length === 0 || 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 // Or the current queen is // the closest attacker in // that direction if (attackers[7].length === 0 || 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 // Or the current queen is // the closest attacker in // that direction if (attackers[1].length === 0 || 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 // Or the current queen is // the closest attacker in // that direction if (attackers[6].length === 0 || 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 // Or the current queen is // the closest attacker in // that direction if (attackers[2].length === 0 || 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 // Or the current queen is // the closest attacker in // that direction if (attackers[5].length === 0 || dis(attackers[5], king) > dis(queens[i], king)) { // Set current queen as // the attacker attackers[5] = queens[i]; } } } for (let i = 0; i < 8; i++) { let f = 1; for (let x of attackers[i]) { if (x !== 0) { f = 0; break; } } if (f === 0) { sol.push(attackers[i]); } } // Return the coordinates return sol;}// Driver Codelet king = [2, 3];let queens = [ [0, 1], [1, 0], [4, 0], [0, 4], [3, 3], [2, 4]];let ans = findQueens(queens, king);print_board(ans);function print_board(ans) { for (let i = 0; i < ans.length; i++) { console.log(ans[i][0] + " " + ans[i][1]); }}// Contributed by sdeadityasharma |
Output:
0 1 2 4 3 3
Time Complexity: O(N), where N is the number of queens
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
