Given two integers N and M denoting the dimensions of a chessboard, and two integers X and Y denoting the King’s position, i.e. the cell (X, Y). The task is to find the number of cells the Queen can visit that are not visited by the King if it gets replaced by the King. The King visits all his adjacent cells and the Queen can move diagonally, horizontally, and vertically.
Examples:
Input: N = 8, M = 8, X = 1, Y = 1
Output: 18
Explanation:
Below is the image to show the movement of King and Queen:
Suppose K represents King and * represents cells visited by the king and Q represents Queen and # represent the cells visited by the queen.
So, the total squares can be visited by the queen is 18.Input: N = 2, M = 1, X = 1, Y = 1
Output: 0
Approach: The idea is to first find the total number of positions that the Queen can visit. Then find the total number of positions that the King can visit. The number of cells that can only be visited by the Queen will be the number of cells the King can visit subtracted from the number of cells the Queen can visit. Follow the below steps to solve the problem:
- Initialize queenMoves by 0 and calculate the total moves of the Queen as follows:
If N – X > 0 and M – Y > 0, queenMoves = queenMoves + min(N – X, M – Y)
If X – 1 > 0 and Y – 1 > 0, queenMoves = queenMoves + min(Y – 1, X – 1)
If X – 1 > 0 and M – Y > 0, queenMoves = queenMoves + min(X – 1, M – Y)
If N – X > 0 and Y – 1 > 0, queenMoves = queenMoves + min(N – X, Y – 1)
At last, add the answer for horizontal and vertical movements as queenMoves = queenMoves + (N – 1) + (M – 1)
- Initialize kingMoves as 0 and calculate King’s moves as follows:
If X + 1 <= N, kingMoves = kingMoves + 1
If X – 1 > 0, kingMoves = kingMoves + 1
If Y + 1 <= M, kingMoves = kingMoves + 1
If Y – 1 > 0, kingMoves = kingMoves + 1
If X + 1 <= N and Y + 1 <= M, kingMoves = kingMoves + 1
If X + 1 <= N and Y – 1 > 0, kingMoves = kingMoves + 1
If X – 1 > 0 and Y – 1 > 0, kingMoves = kingMoves + 1
If X – 1 > 0 and Y + 1 <= M, kingMoves = kingMoves + 1
- Print the absolute difference between the Queen’s and King’s calculated in the above steps as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to print the number of cells// only visited by the queenint Moves_Calculator(int x, int y, int row, int col){ // Find all the moves int total_moves = 0; // Find all moves for x + 1, y + 1 if ((row - x) > 0 && (col - y) > 0) total_moves += min((row - x), (col - y)); // Find all moves for x - 1, y - 1 if ((y - 1) > 0 && (x - 1) > 0) total_moves += min((y - 1), (x - 1)); // Find all moves for x - 1, y + 1 if ((x - 1) > 0 && (col - y) > 0) total_moves += min((x - 1), (col - y)); // Find all moves for x + 1, y - 1 if ((row - x) > 0 && (y - 1) > 0) total_moves += min((row - x), (y - 1)); total_moves += (row - 1) + (col - 1); // Find all squares visited by King // x + 1, in same row int king_moves = 0; if (x + 1 <= row) king_moves += 1; // x - 1, in same row if (x - 1 > 0) king_moves += 1; // y + 1, in same column if (y + 1 <= col) king_moves += 1; // y - 1, in same column if (y - 1 > 0) king_moves += 1; if (x + 1 <= row && y + 1 <= col) king_moves += 1; if (x + 1 <= row && y - 1 > 0) king_moves += 1; if (x - 1 > 0 && y - 1 > 0) king_moves += 1; if (x - 1 > 0 && y + 1 <= col) king_moves += 1; // Return answer return total_moves - king_moves;}// Driver Codeint main(){ // Dimension of Board int n = 8, m = 8; // Position of Cell int x = 1, y = 1; // Function Call cout << (Moves_Calculator(x, y, m, n)); return 0;}// This code is contributed by akhilsaini |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to print the number of cells// only visited by the queenstatic int Moves_Calculator(int x, int y, int row, int col){ // Find all the moves int total_moves = 0; // Find all moves for x + 1, y + 1 if ((row - x) > 0 && (col - y) > 0) total_moves += Math.min((row - x), (col - y)); // Find all moves for x - 1, y - 1 if ((y - 1) > 0 && (x - 1) > 0) total_moves += Math.min((y - 1), (x - 1)); // Find all moves for x - 1, y + 1 if ((x - 1) > 0 && (col - y) > 0) total_moves += Math.min((x - 1), (col - y)); // Find all moves for x + 1, y - 1 if ((row - x) > 0 && (y - 1) > 0) total_moves += Math.min((row - x), (y - 1)); total_moves += (row - 1) + (col - 1); // Find all squares visited by King // x + 1, in same row int king_moves = 0; if (x + 1 <= row) king_moves += 1; // x - 1, in same row if (x - 1 > 0) king_moves += 1; // y + 1, in same column if (y + 1 <= col) king_moves += 1; // y - 1, in same column if (y - 1 > 0) king_moves += 1; if (x + 1 <= row && y + 1 <= col) king_moves += 1; if (x + 1 <= row && y - 1 > 0) king_moves += 1; if (x - 1 > 0 && y - 1 > 0) king_moves += 1; if (x - 1 > 0 && y + 1 <= col) king_moves += 1; // Return answer return total_moves - king_moves;}// Driver Codepublic static void main(String[] args){ // Dimension of Board int n = 8, m = 8; // Position of Cell int x = 1, y = 1; // Function Call System.out.println(Moves_Calculator(x, y, m, n));}}// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach# Function to print the number of cells# only visited by the queendef Moves_Calculator(x, y, row, col): # Find all the moves total_moves = 0 # Find all moves for x + 1, y + 1 if (row - x) > 0 and (col - y) > 0: total_moves += min((row - x), (col - y)) # Find all moves for x - 1, y - 1 if (y - 1) > 0 and (x - 1) > 0: total_moves += min((y - 1), (x - 1)) # Find all moves for x - 1, y + 1 if (x - 1) > 0 and (col - y) > 0: total_moves += min((x - 1), (col - y)) # Find all moves for x + 1, y - 1 if (row - x) > 0 and (y - 1) > 0: total_moves += min((row - x), (y - 1)) total_moves += (row - 1) + (col - 1) # Find all squares visited by King # x + 1, in same row king_moves = 0 if x + 1 <= m: king_moves += 1 # x - 1, in same row if x - 1 > 0: king_moves += 1 # y + 1, in same column if y + 1 <= n: king_moves += 1 # y - 1, in same column if y - 1 > 0: king_moves += 1 if x + 1 <= m and y + 1 <= n: king_moves += 1 if x + 1 <= m and y - 1 > 0: king_moves += 1 if x - 1 > 0 and y - 1 > 0: king_moves += 1 if x - 1 > 0 and y + 1 <= n: king_moves += 1 # Return answer return total_moves - king_moves# Driver Codeif __name__ == '__main__': # Dimension of Board n, m = 8, 8 # Position of Cell x, y = 1, 1 # Function Call print(Moves_Calculator(x, y, m, n)) |
C#
// C# program for the above approachusing System;class GFG{// Function to print the number of cells// only visited by the queenstatic int Moves_Calculator(int x, int y, int row, int col){ // Find all the moves int total_moves = 0; // Find all moves for x + 1, y + 1 if ((row - x) > 0 && (col - y) > 0) total_moves += Math.Min((row - x), (col - y)); // Find all moves for x - 1, y - 1 if ((y - 1) > 0 && (x - 1) > 0) total_moves += Math.Min((y - 1), (x - 1)); // Find all moves for x - 1, y + 1 if ((x - 1) > 0 && (col - y) > 0) total_moves += Math.Min((x - 1), (col - y)); // Find all moves for x + 1, y - 1 if ((row - x) > 0 && (y - 1) > 0) total_moves += Math.Min((row - x), (y - 1)); total_moves += (row - 1) + (col - 1); // Find all squares visited by King // x + 1, in same row int king_moves = 0; if (x + 1 <= row) king_moves += 1; // x - 1, in same row if (x - 1 > 0) king_moves += 1; // y + 1, in same column if (y + 1 <= col) king_moves += 1; // y - 1, in same column if (y - 1 > 0) king_moves += 1; if (x + 1 <= row && y + 1 <= col) king_moves += 1; if (x + 1 <= row && y - 1 > 0) king_moves += 1; if (x - 1 > 0 && y - 1 > 0) king_moves += 1; if (x - 1 > 0 && y + 1 <= col) king_moves += 1; // Return answer return total_moves - king_moves;}// Driver Codepublic static void Main(){ // Dimension of Board int n = 8, m = 8; // Position of Cell int x = 1, y = 1; // Function Call Console.WriteLine(Moves_Calculator(x, y, m, n));}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program for the above approach// Function to print the number of cells// only visited by the queenfunction Moves_Calculator(x, y, row, col){ // Find all the moves let total_moves = 0; // Find all moves for x + 1, y + 1 if ((row - x) > 0 && (col - y) > 0) total_moves += Math.min((row - x), (col - y)); // Find all moves for x - 1, y - 1 if ((y - 1) > 0 && (x - 1) > 0) total_moves += Math.min((y - 1), (x - 1)); // Find all moves for x - 1, y + 1 if ((x - 1) > 0 && (col - y) > 0) total_moves += Math.min((x - 1), (col - y)); // Find all moves for x + 1, y - 1 if ((row - x) > 0 && (y - 1) > 0) total_moves += Math.min((row - x), (y - 1)); total_moves += (row - 1) + (col - 1); // Find all squares visited by King // x + 1, in same row let king_moves = 0; if (x + 1 <= row) king_moves += 1; // x - 1, in same row if (x - 1 > 0) king_moves += 1; // y + 1, in same column if (y + 1 <= col) king_moves += 1; // y - 1, in same column if (y - 1 > 0) king_moves += 1; if (x + 1 <= row && y + 1 <= col) king_moves += 1; if (x + 1 <= row && y - 1 > 0) king_moves += 1; if (x - 1 > 0 && y - 1 > 0) king_moves += 1; if (x - 1 > 0 && y + 1 <= col) king_moves += 1; // Return answer return total_moves - king_moves;}// Driver code// Dimension of Boardlet n = 8, m = 8;// Position of Celllet x = 1, y = 1;// Function Calldocument.write(Moves_Calculator(x, y, m, n));// This code is contributed by splevel62 </script> |
18
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!