Count positions in a chessboard that can be visited by the Queen which are not visited by the King

Photo of Namachila Namachila Send an email 3 days ago
0 0 9 minutes read

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 queen
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 += 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 Code
int 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 approach


import java.io.*;


 


class GFG{


 


// Function to print the number of cells


// only visited by the queen


static 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 Code


public 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 queen


def 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 Code


if __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 approach


using System;


 


class GFG{


 


// Function to print the number of cells


// only visited by the queen


static 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 Code


public 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 queen


function 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 Board


let n = 8, m = 8;


 


// Position of Cell


let x = 1, y = 1;


 


// Function Call


document.write(Moves_Calculator(x, y, m, n));


 


// This code is contributed by splevel62   


 


</script>










































Output: 


18


 




Time Complexity: O(1)
Auxiliary Space: O(1)





                                            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 zambiatek!







			
		


				

			

				

						
							Photo of Namachila
						
					Namachila
						
							
							Send an email
						
					3 days ago
0 0  9 minutes read 


		

					

		


		

		

		

		
	


	
	


		
		


								

						
							Photo of Namachila						
					

					
			


											
Namachila

						
				

									


							

			

		

		


	





			

			
			

			

	

				


					

						
Related Articles

					


					


					
							


								
			
								
Ninja Gaiden Ragebound finally gives this franchise its Super Castlevania 4 moment


								
2 minutes ago
							


						
							


								
			
								
The Google Photos video editor upgrades you’ve been waiting for are finally on their way


								
3 minutes ago
							


						
							


								
			
								
New leak all but confirms Samsung’s move away from base and Plus S-series models


								
3 minutes ago
							


						
							


								
			
								
A forgotten Sony gaming phone is being reimagined for 2025


								
4 minutes ago
							


						
					

				


				


		

		
	

		
Leave a Reply 
Your email address will not be published. Required fields are marked *
 
 



 


 


 


	

	

	



	


	




	

	
	
	






		

		
		
			
			Back to top button