Dado un tablero de ajedrez de N x N y la posición de X alfiles en él, la tarea es calcular el número de parejas de alfiles que se atacan entre sí. Tenga en cuenta que al considerar un par de alfiles, no se considera que todos los demás alfiles estén en el tablero.
Ejemplo:
Entrada: N = 5, alfiles[][] = {{2, 1}, {3, 2}, {2, 3}}
Salida: 2
Explicación: Los alfiles en las posiciones {2, 1} y {3, 2} y los alfiles en las posiciones {3, 2} y {2, 3} se atacan entre sí.Entrada: N = 10, alfiles[][] = {{1, 1}, {1, 5}, {3, 3}, {5, 1}, {5, 5}}
Salida: 6
Enfoque: El problema dado se puede resolver usando combinatoria básica . Como todos los alfiles que se encuentran en la misma diagonal se atacarán entre sí, todas las posibles parejas de alfiles que se encuentren en la misma diagonal que se puedan formar se atacarán entre sí. Por lo tanto, recorra la array para todas las diagonales en las direcciones izquierda y derecha y cuente el número de alfiles en la diagonal actual en un cnt variable . Ahora, para cada diagonal, el número de alfiles atacantes será cnt C 2 .
A continuación se muestra la implementación del enfoque anterior:
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 code
int 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 approach board = [[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 code N = 10 bishops = [[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>
Producción
6
Complejidad temporal: O(N * N)
Espacio auxiliar: O(N * N)