Given a N x N chessboard and the position of X bishops on it, the task is to calculate the count of pairs of bishops such that they attack each other. Note that while considering a pair of bishops, all the other bishops are not considered to be on the board.
Example:
Input: N = 5, bishops[][] = {{2, 1}, {3, 2}, {2, 3}}
Output: 2
Explanation: The bishops on the positions {2, 1} and {3, 2} and bishops on the positions {3, 2} and {2, 3} attack each other.Input: N = 10, bishops[][] = {{1, 1}, {1, 5}, {3, 3}, {5, 1}, {5, 5}}
Output: 6
Â
Approach: The given problem can be solved using basic combinatorics. Since all the bishops that lie on the same diagonal will attack each other, all possible pairs of bishops that are on the same diagonal that can be formed will attack each other. Therefore, traverse the matrix for all diagonals in both left and right directions and count the number of bishops on the current diagonal in a variable cnt. Now for each diagonal, the number of attacking bishops will be cntC2.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;Â
int board[20][20];Â
int countPairs(int N, vector<pair<int, int> > bishops){Â Â Â Â // Set all bits to 0Â Â Â Â memset(board, 0, sizeof(board));Â
    // Set all the bits    // having bishop to 1    for (int i = 0; i < bishops.size(); i++) {        board[bishops[i].first][bishops[i].second] = 1;    }Â
    // Stores the final answer    int ans = 0;Â
    // Loop to traverse the matrix    // diagonally in left direction    for (int s = 2; s <= 2 * N; s++) {Â
        // Stores count of bishop        // in the current diagonal        int cnt = 0;Â
        for (int i = 1, j = s - i;             max(i, j) <= min(N, s - 1); i++, j--) {            if (board[j][i - j] == 1)Â
                // Update cnt                cnt++;        }Â
        // Update the answer        if (cnt > 1)            ans += ((cnt + 1) * cnt) / 2;    }Â
    // Loop to traverse the matrix    // diagonally in right direction    for (int s = 2; s <= 2 * N; s++) {Â
        // Stores count of bishop        // in the current diagonal        int cnt = 0;Â
        for (int i = 1, j = s - i;             max(i, j) <= min(N, s - 1); i++, j--) {            if (board[i][N - j + 1] == 1)Â
                // Update cnt                cnt++;        }Â
        // Update the answer        if (cnt > 1)            ans += ((cnt + 1) * cnt) / 2;    }Â
    // Return answer    return ans;}Â
// Driver codeint main(){Â Â Â Â int N = 10;Â Â Â Â vector<pair<int, int> > bishops = {Â Â Â Â Â Â Â Â { 1, 1 }, { 1, 5 }, { 3, 3 }, { 5, 1 }, { 5, 5 }Â Â Â Â };Â
    cout << countPairs(N, bishops);Â
    return 0;} |
Java
import java.util.*;class GFG{Â Â static int [][]board = new int[20][20];Â
  static int countPairs(int N, int[][] bishops)  {Â
    // Set all the bits    // having bishop to 1    for (int i = 0; i < bishops.length; i++) {      board[bishops[i][0]][bishops[i][1]] = 1;    }Â
    // Stores the final answer    int ans = 0;Â
    // Loop to traverse the matrix    // diagonally in left direction    for (int s = 2; s <= 2 * N; s++) {Â
      // Stores count of bishop      // in the current diagonal      int cnt = 0;Â
      for (int i = 1, j = s - i;           Math.max(i, j) <= Math.min(N, s - 1)&&i-j>0; i++, j--) {        if (board[j][i - j] == 1)Â
          // Update cnt          cnt++;      }Â
      // Update the answer      if (cnt > 1)        ans += ((cnt + 1) * cnt) / 2;    }Â
    // Loop to traverse the matrix    // diagonally in right direction    for (int s = 2; s <= 2 * N; s++) {Â
      // Stores count of bishop      // in the current diagonal      int cnt = 0;Â
      for (int i = 1, j = s - i;           Math.max(i, j) <= Math.min(N, s - 1); i++, j--) {        if (board[i][N - j + 1] == 1)Â
          // Update cnt          cnt++;      }Â
      // Update the answer      if (cnt > 1)        ans += ((cnt + 1) * cnt) / 2;    }Â
    // Return answer    return ans;  }Â
  // Driver code  public static void main(String[] args)  {    int N = 10;    int[][] bishops = {      { 1, 1 }, { 1, 5 }, { 3, 3 }, { 5, 1 }, { 5, 5 }    };Â
    System.out.print(countPairs(N, bishops));Â
  }}Â
// This code is contributed by 29AjayKumar |
Python3
# Python program for above approachboard = [[0 for i in range(20)] for j in range(20)]Â
def countPairs(N, bishops):Â
    # Set all the bits    # having bishop to 1    for i in range(len(bishops)):        board[bishops[i][0]][bishops[i][1]] = 1Â
    # Stores the final answer    ans = 0Â
    # Loop to traverse the matrix    # diagonally in left direction    for s in range(2, (2 * N) + 1):Â
        # Stores count of bishop        # in the current diagonal        cnt = 0Â
        i = 1        j = s - i        while(max(i, j) <= min(N, s - 1)):            if (board[j][i - j] == 1):                # Update cnt                cnt += 1            i += 1            j -= 1Â
        # Update the answer        if (cnt > 1):            ans += ((cnt + 1) * cnt) // 2Â
    # Loop to traverse the matrix    # diagonally in right direction    for s in range(2, (2 * N) + 1):Â
        # Stores count of bishop        # in the current diagonal        cnt = 0Â
        i = 1        j = s - i        while(max(i, j) <= min(N, s - 1)):                        if (board[i][N - j + 1] == 1):                # Update cnt                cnt += 1            i += 1            j -= 1Â
        # Update the answer        if (cnt > 1):            ans += ((cnt + 1) * cnt) // 2Â
    # Return answer    return ansÂ
# Driver codeN = 10bishops = [[1, 1], [1, 5], [3, 3], [5, 1], [5, 5]]print(countPairs(N, bishops))Â
# This code is contributed by gfgking |
C#
using System;class GFG{Â Â Â Â static int[,] board = new int[20,20];Â Â Â Â static int countPairs(int N, int[,] bishops)Â Â Â Â {Â
        // Set all the bits        // having bishop to 1        for (int i = 0; i < bishops.GetLength(0); i++)        {            board[bishops[i,0], bishops[i,1]] = 1;        }Â
        // Stores the final answer        int ans = 0;Â
        // Loop to traverse the matrix        // diagonally in left direction        for (int s = 2; s <= 2 * N; s++)        {Â
            // Stores count of bishop            // in the current diagonal            int cnt = 0;Â
            for (int i = 1, j = s - i;                 Math.Max(i, j) <= Math.Min(N, s - 1) && i - j > 0; i++, j--)            {                if (board[j,i - j] == 1)Â
                    // Update cnt                    cnt++;            }Â
            // Update the answer            if (cnt > 1)                ans += ((cnt + 1) * cnt) / 2;        }Â
        // Loop to traverse the matrix        // diagonally in right direction        for (int s = 2; s <= 2 * N; s++)        {Â
            // Stores count of bishop            // in the current diagonal            int cnt = 0;Â
            for (int i = 1, j = s - i;                 Math.Max(i, j) <= Math.Min(N, s - 1); i++, j--)            {                if (board[i,N - j + 1] == 1)Â
                    // Update cnt                    cnt++;            }Â
            // Update the answer            if (cnt > 1)                ans += ((cnt + 1) * cnt) / 2;        }Â
        // Return answer        return ans;    }Â
    // Driver code    public static void Main()    {        int N = 10;        int[,] bishops = new int[5, 2]{{ 1, 1 }, { 1, 5 }, { 3, 3 }, { 5, 1 }, { 5, 5 }};Â
        Console.Write(countPairs(N, bishops));Â
    }}Â
// This code is contributed by Saurabh Jaiswal |
Javascript
<script>             // JavaScript program for above approach    let board = new Array(20).fill(0).map(() => new Array(20).fill(0));Â
    const countPairs = (N, bishops) => {Â
        // Set all the bits        // having bishop to 1        for (let i = 0; i < bishops.length; i++) {            board[bishops[i][0]][bishops[i][1]] = 1;        }Â
        // Stores the final answer        let ans = 0;Â
        // Loop to traverse the matrix        // diagonally in left direction        for (let s = 2; s <= 2 * N; s++) {Â
            // Stores count of bishop            // in the current diagonal            let cnt = 0;Â
            for (let i = 1, j = s - i;                Math.max(i, j) <= Math.min(N, s - 1); i++, j--) {                if (board[j][i - j] == 1)Â
                    // Update cnt                    cnt++;            }Â
            // Update the answer            if (cnt > 1)                ans += ((cnt + 1) * cnt) / 2;        }Â
        // Loop to traverse the matrix        // diagonally in right direction        for (let s = 2; s <= 2 * N; s++) {Â
            // Stores count of bishop            // in the current diagonal            let cnt = 0;Â
            for (let i = 1, j = s - i;                Math.max(i, j) <= Math.min(N, s - 1); i++, j--) {                if (board[i][N - j + 1] == 1)Â
                    // Update cnt                    cnt++;            }Â
            // Update the answer            if (cnt > 1)                ans += ((cnt + 1) * cnt) / 2;        }Â
        // Return answer        return ans;    }Â
    // Driver code    let N = 10;    let bishops = [        [1, 1], [1, 5], [3, 3], [5, 1], [5, 5]    ];Â
    document.write(countPairs(N, bishops));Â
// This code is contributed by rakeshsahniÂ
</script> |
Output
6
Time Complexity: O(N * N)
Auxiliary Space: O(N * 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!
