Given an integer N and bishop position {x, y}, the task is to print all possible sets of points that the bishop can reach in one move on an N*N chessboard.
Note: Output the points in sorted order.
Examples:
Input: n = 2, x = 0, y = 0
Output: (0, 0), (1, 1)Input: n = 3, x = 1, y=1
Output: (0, 0), (0, 2), (1, 1) (2, 0), (2, 2)
Naive Approach: This can be solved with the following idea:
A bishop can only travel diagonally on a chessboard. Consider the diagonal points from the given point (i, j).
Below are the steps involved in the implementation of the code:
- Make vector pairs in order to store the points.
- Add the current position of the bishop in the vector.
- Check for the points that can be reached near the given point.
- Make sure not to move outside the boundaries of the chessboard.
- Now sort the points in lexicographical order.
- Check for duplicate points and finally print the points.
Below is the implementation of the above approach:
C++
// C++ Implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to print all possible positions // of bishop void positionofbishop(int n, int x, int y) { vector<pair<int, int> > points; // Add current position points.push_back({ x, y }); // Calculate possible points // in top left direction for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) { points.push_back({ i, j }); } // Calculate possible points // in top right direction for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) { points.push_back({ i, j }); } // Calculate possible points // in bottom left direction for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) { points.push_back({ i, j }); } // Calculate possible points // in bottom right direction for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) { points.push_back({ i, j }); } // sort the points in // lexicographical order sort(points.begin(), points.end()); // Remove duplicates auto last = unique(points.begin(), points.end()); points.erase(last, points.end()); // Print all possible points for (auto p : points) { cout << "(" << p.first << ", " << p.second << ")" << endl; } } // Driver code int main() { int n = 3, x = 1, y = 1; // Function call positionofbishop(n, x, y); return 0; }
Java
// Java Implementation of the above approach import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Objects; public class GFG { // Function to print all possible positions // of bishop public static void positionOfBishop(int n, int x, int y) { List<Point> points = new ArrayList<>(); // Add current position points.add(new Point(x, y)); // Calculate possible points in top left direction for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) { points.add(new Point(i, j)); } // Calculate possible points in top right direction for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) { points.add(new Point(i, j)); } // Calculate possible points in bottom left // direction for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) { points.add(new Point(i, j)); } // Calculate possible points in bottom right // direction for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) { points.add(new Point(i, j)); } // Sort the points in lexicographical order Collections.sort(points); // Remove duplicates List<Point> uniquePoints = new ArrayList<>(); Point prev = null; for (Point p : points) { if (!Objects.equals(p, prev)) { uniquePoints.add(p); prev = p; } } // Print all possible points for (Point p : uniquePoints) { System.out.println("(" + p.x + ", " + p.y + ")"); } } public static void main(String[] args) { int n = 3, x = 1, y = 1; // Function call positionOfBishop(n, x, y); } // Implements the Comparable interface, meaning that it // can be compared to other Point objects private static class Point implements Comparable<Point> { int x, y; // constructor that initializes the instance // variables x and y with the values provided as // arguments Point(int x, int y) { this.x = x; this.y = y; } // overrides the compareTo method of the Comparable // interface to compare two Point objects based on // their x and y coordinates @Override public int compareTo(Point other) { // If the x coordinates of the two points are // equal, then the y coordinates are compared. // The class overrides the equals method to // compare two Point objects for equality based // on their x and y coordinates. if (this.x == other.x) { return Integer.compare(this.y, other.y); } else { return Integer.compare(this.x, other.x); } } // overrides the equals method to compare two Point objects for // equality based on their x and y coordinates. @Override public boolean equals(Object obj) { if (obj instanceof Point) { Point other = (Point)obj; return this.x == other.x && this.y == other.y; } return false; } // overrides the hashCode method to generate a hash // code for a Point object based on its x and y // coordinates. @Override public int hashCode() { return Objects.hash(x, y); } } }
Python3
# Python Implementation of the above approach from collections import OrderedDict # Function to print all possible positions # of bishop def positionofbishop(n, x, y): points = [] # Add current position points.append((x, y)) # Calculate possible points # in top left direction i, j = x - 1, y - 1 while i >= 0 and j >= 0: points.append((i, j)) i -= 1 j -= 1 # Calculate possible points # in top right direction i, j = x - 1, y + 1 while i >= 0 and j < n: points.append((i, j)) i -= 1 j += 1 # Calculate possible points # in bottom left direction i, j = x + 1, y - 1 while i < n and j >= 0: points.append((i, j)) i += 1 j -= 1 # Calculate possible points # in bottom right direction i, j = x + 1, y + 1 while i < n and j < n: points.append((i, j)) i += 1 j += 1 # Sort the points in lexicographical order points.sort() # Remove duplicates points = list(OrderedDict.fromkeys(points)) # Print all possible points for p in points: print("({0}, {1})".format(p[0], p[1])) # Driver code if __name__ == '__main__': n, x, y = 3, 1, 1 # Function call positionofbishop(n, x, y) # This code is contributed by Susobhan Akhuli
C#
// C# Implementation of the above approach using System; using System.Collections.Generic; using System.Linq; public class Program { // Function to print all possible positions // of bishop public static void PositionOfBishop(int n, int x, int y) { List<Tuple<int, int> > points = new List<Tuple<int, int> >(); // Add current position points.Add(Tuple.Create(x, y)); // Calculate possible points // in top left direction for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) { points.Add(Tuple.Create(i, j)); } // Calculate possible points // in top right direction for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) { points.Add(Tuple.Create(i, j)); } // Calculate possible points // in bottom left direction for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) { points.Add(Tuple.Create(i, j)); } // Calculate possible points // in bottom right direction for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) { points.Add(Tuple.Create(i, j)); } // Sort the points in lexicographical order points.Sort(); // Remove duplicates points = points.Distinct().ToList(); // Print all possible points foreach(var p in points) { Console.WriteLine($ "({p.Item1}, {p.Item2})"); } } // Driver code public static void Main() { int n = 3, x = 1, y = 1; // Function call PositionOfBishop(n, x, y); } }
Javascript
// Function to print all possible positions of bishop function positionofbishop(n, x, y) { const points = []; // Add current position points.push([x, y]); // Calculate possible points in top left direction for (let i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) { points.push([i, j]); } // Calculate possible points in top right direction for (let i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) { points.push([i, j]); } // Calculate possible points in bottom left direction for (let i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) { points.push([i, j]); } // Calculate possible points in bottom right direction for (let i = x + 1, j = y + 1; i < n && j < n; i++, j++) { points.push([i, j]); } // Sort the points in lexicographical order points.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // Remove duplicates const uniquePoints = []; for (const point of points) { if (!uniquePoints.some(p => p[0] === point[0] && p[1] === point[1])) { uniquePoints.push(point); } } // Print all possible points for (const p of uniquePoints) { console.log(`(${p[0]}, ${p[1]})`); } } // Driver code const n = 3; const x = 1; const y = 1; // Function call positionofbishop(n, x, y);
(0, 0) (0, 2) (1, 1) (2, 0) (2, 2)
Time Complexity: O(n2)
Auxiliary Space: O(n)
Optimal Approach:
The idea is to traverse the board in four directions (top-left, top-right, bottom-left, bottom-right) and stop when we hit the edge of the board or a diagonal that intersects with the bishop’s current diagonal. By doing so, we can guarantee that we only visit each square once and avoid sorting the points or using extra memory to store them.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to print all possible points // where bishop can reach void positionofbishop(int n, int x, int y) { vector<pair<int, int> > points; // Add current position points.push_back({ x, y }); // Calculate number of squares // in the top-left diagonal int tl = min(x, y); // Calculate number of squares // in the top-right diagonal int tr = min(x, n - 1 - y); // Calculate number of squares // in the bottom-left diagonal int bl = min(n - 1 - x, y); // Calculate number of squares // in the bottom-right diagonal int br = min(n - 1 - x, n - 1 - y); // Add all possible points for (int i = 1; i <= tl; i++) { points.push_back({ x - i, y - i }); } for (int i = 1; i <= tr; i++) { points.push_back({ x - i, y + i }); } for (int i = 1; i <= bl; i++) { points.push_back({ x + i, y - i }); } for (int i = 1; i <= br; i++) { points.push_back({ x + i, y + i }); } // Print all possible points // in sorted order sort(points.begin(), points.end()); for (auto p : points) { cout << "(" << p.first << ", " << p.second << ")" << endl; } } // Driver code int main() { int n = 3, x = 1, y = 1; // Function call positionofbishop(n, x, y); return 0; }
Java
// Java code for the approach import java.awt.Point; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; public class GFG { // Function to print all possible points // where bishop can reach public static void positionOfBishop(int n, int x, int y) { ArrayList<Point> points = new ArrayList<>(); // Add current position points.add(new Point(x, y)); // Calculate number of squares // in the top-left diagonal int tl = Math.min(x, y); // Calculate number of squares // in the top-right diagonal int tr = Math.min(x, n - 1 - y); // Calculate number of squares // in the bottom-left diagonal int bl = Math.min(n - 1 - x, y); // Calculate number of squares // in the bottom-right diagonal int br = Math.min(n - 1 - x, n - 1 - y); // Add all possible points for (int i = 1; i <= tl; i++) { points.add(new Point(x - i, y - i)); } for (int i = 1; i <= tr; i++) { points.add(new Point(x - i, y + i)); } for (int i = 1; i <= bl; i++) { points.add(new Point(x + i, y - i)); } for (int i = 1; i <= br; i++) { points.add(new Point(x + i, y + i)); } // Sort the points in ascending order of x-coordinate // and then y-coordinate Collections.sort(points, new Comparator<Point>() { public int compare(Point p1, Point p2) { if (p1.x != p2.x) { return Integer.compare(p1.x, p2.x); } else { return Integer.compare(p1.y, p2.y); } } }); // Print all possible points for (Point p : points) { System.out.println("(" + p.x + ", " + p.y + ")"); } } // Driver code public static void main(String[] args) { int n = 3, x = 1, y = 1; // Function call positionOfBishop(n, x, y); } }
Python3
# Function to print all possible points # where bishop can reach def positionofbishop(n, x, y): points = [] # Add current position points.append((x, y)) # Calculate number of squares # in the top-left diagonal tl = min(x, y) # Calculate number of squares # in the top-right diagonal tr = min(x, n - 1 - y) # Calculate number of squares # in the bottom-left diagonal bl = min(n - 1 - x, y) # Calculate number of squares # in the bottom-right diagonal br = min(n - 1 - x, n - 1 - y) # Add all possible points for i in range(1, tl+1): points.append((x - i, y - i)) for i in range(1, tr+1): points.append((x - i, y + i)) for i in range(1, bl+1): points.append((x + i, y - i)) for i in range(1, br+1): points.append((x + i, y + i)) # Print all possible points # in sorted order points.sort() for p in points: print(f"({p[0]}, {p[1]})") # Driver code if __name__ == '__main__': n, x, y = 3, 1, 1 # Function call positionofbishop(n, x, y)
C#
// C# code for the above approach: using System; using System.Collections.Generic; using System.Linq; public class Program { // Function to print all possible points // where bishop can reach public static void PositionOfBishop(int n, int x, int y) { List<Tuple<int, int> > points = new List<Tuple<int, int> >(); // Add current position points.Add(new Tuple<int, int>(x, y)); // Calculate number of squares // in the top-left diagonal int tl = Math.Min(x, y); // Calculate number of squares // in the top-right diagonal int tr = Math.Min(x, n - 1 - y); // Calculate number of squares // in the bottom-left diagonal int bl = Math.Min(n - 1 - x, y); // Calculate number of squares // in the bottom-right diagonal int br = Math.Min(n - 1 - x, n - 1 - y); // Add all possible points for (int i = 1; i <= tl; i++) { points.Add(new Tuple<int, int>(x - i, y - i)); } for (int i = 1; i <= tr; i++) { points.Add(new Tuple<int, int>(x - i, y + i)); } for (int i = 1; i <= bl; i++) { points.Add(new Tuple<int, int>(x + i, y - i)); } for (int i = 1; i <= br; i++) { points.Add(new Tuple<int, int>(x + i, y + i)); } // Print all possible points // in sorted order points.Sort(); foreach(var p in points) { Console.WriteLine("(" + p.Item1 + ", " + p.Item2 + ")"); } } // Driver code public static void Main() { int n = 3, x = 1, y = 1; // Function call PositionOfBishop(n, x, y); } }
Javascript
function positionofbishop(n, x, y) { let points = []; // Add current position points.push([x, y]); // Calculate number of squares // in the top-left diagonal let tl = Math.min(x, y); // Calculate number of squares // in the top-right diagonal let tr = Math.min(x, n - 1 - y); // Calculate number of squares // in the bottom-left diagonal let bl = Math.min(n - 1 - x, y); // Calculate number of squares // in the bottom-right diagonal let br = Math.min(n - 1 - x, n - 1 - y); // Add all possible points for (let i = 1; i <= tl; i++) { points.push([x - i, y - i]); } for (let i = 1; i <= tr; i++) { points.push([x - i, y + i]); } for (let i = 1; i <= bl; i++) { points.push([x + i, y - i]); } for (let i = 1; i <= br; i++) { points.push([x + i, y + i]); } // Print all possible points // in sorted order points.sort(); for (let p of points) { console.log(`(${p[0]}, ${p[1]})`); } } // Driver code let n = 3, x = 1, y = 1; // Function call positionofbishop(n, x, y);
(0, 0) (0, 2) (1, 1) (2, 0) (2, 2)
Time Complexity: O(nlogn)
Auxiliary Space: O(1)