Dado un número entero N y una array arr[] de posiciones que denota las posiciones de las torres no atacantes ya colocadas, la tarea es encontrar las posiciones de las torres no atacantes en orden lexicográfico que se pueden colocar en el tablero de ajedrez N*N.
Movimiento de torres: cualquier torre puede moverse horizontal o verticalmente cualquier número de casillas desocupadas.
Ejemplos:
Entrada: N = 4, arr[] = {(1, 4), (2, 2)}
Salida: 2
3 1
4 3
Explicación:
Puede haber dos torres más que se pueden colocar en el tablero de ajedrez 4*4
Entrada: N = 5, arr[] = {}
Salida: 5
1 1
2 2
3 3
4 4
5 5
Enfoque ingenuo: Inicialice una array mat[][] 2D de tamaño N*N con 0 en cada celda y márquela como torres para las posiciones iniciales de las torres en 1. Luego recorra la array mat[][], verificando si i -ésima fila y La j -ésima columna contiene cualquier torre, Manteniendo un conteo de torres colocadas. Si alguna fila contiene y la columna no contiene ninguna torre colocada, coloque una torre allí y agregue esta celda a su string de resultados.
Finalmente, imprima el conteo de torres colocadas y las posiciones de la colocación de las torres
Complejidad de tiempo: O(N 3 )
Complejidad de espacio: O(N 2 )
Enfoque eficiente: La idea es crear dos arrays de Ntamaño de cada uno, para almacenar si la i -ésima fila o la i -ésima columna contiene alguna torre o no y ahora será eficiente buscar si esta fila y la columna correspondiente ya contienen Torre o no.
Complejidad de tiempo: O(N 2 )
Complejidad de espacio: O(N)
Aproximación más eficiente: La observación clave en el problema es que la máxima torre que se puede colocar es NK . Es decir, dos torres se atacan si están en la misma fila o en la misma columna. Dado que dos de las torres dadas no se atacan entre sí, todas las filas dadas en la entrada son únicas. De manera similar, todas las columnas dadas en la entrada son únicas. Entonces, nos quedan NK filas sin usar y NK columnas sin usar para colocar las nuevas torres.
En otras palabras, si tratamos de poner más de NK torres por el Principio de Pigeonhole , si hay N+1 palomas y N lugares para llenar, entonces al menos un lugar contiene más de 1 paloma.
Y para encontrar la respuesta lexicográficamente mínima. Esta respuesta se puede lograr emparejando la fila más pequeña sin usar con la columna más pequeña sin usar, la segunda fila más pequeña sin usar con la segunda columna más pequeña sin usar y así sucesivamente.
Complejidad de tiempo: O(N)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find
// count of placing non-attacking
// rooks on the N x N chessboard
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of
// placing non-attacking rooks
// on the N x N chessboard
void findCountRooks(int row[], int col[],
int n, int k)
{
// Count of the Non-attacking rooks
int res = n - k;
cout << res << "\n";
int ri = 0, ci = 0;
while (res-- > 0)
{
// Printing lexicographically
// smallest configuration
while (ri < k && row[ri] == 1)
{
ri++;
}
while (ci < k && col[ci] == 1)
{
ci++;
}
cout << (ri + 1) << " "
<< (ci + 1) << "\n";
ri++;
ci++;
}
}
// Driver Code
int main()
{
int n = 4;
int k = 2;
int row[] = { 1, 2 };
int col[] = { 4, 2 };
// Function call
findCountRooks(row, col, n, k);
return 0;
}
// This code is contributed by jana_sayantan
Java
// Java implementation to find
// count of placing non-attacking
// rooks on the N x N chessboard
import java.util.Scanner;
public class P2Placerooks {
// Function to find the count of
// placing non-attacking rooks
// on the N x N chessboard
static void findCountRooks(
int row[], int col[], int n, int k)
{
// Count of the Non-attacking rooks
int res = n - k;
System.out.println(res + " ");
int ri = 0, ci = 0;
while (res-- > 0) {
// Printing lexicographically
// smallest configuration
while (ri < k && row[ri] == 1) {
ri++;
}
while (ci < k && col[ci] == 1) {
ci++;
}
System.out.println((ri + 1)
+ " " + (ci + 1)
+ " ");
ri++;
ci++;
}
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
int k = 2;
int row[] = { 1, 2 };
int col[] = { 4, 2 };
// Function Call
findCountRooks(row, col, n, k);
}
}
Python3
# Python3 implementation to find # count of placing non-attacking # rooks on the N x N chessboard # Function to find the count of # placing non-attacking rooks # on the N x N chessboard def findCountRooks(row, col, n, k): # Count of the Non-attacking rooks res = n - k print(res) ri = 0 ci = 0 while (res > 0): # Printing lexicographically # smallest configuration while (ri < k and row[ri] == 1): ri += 1 while (ci < k and col[ci] == 1): ci += 1 print((ri + 1), "", (ci + 1)) ri += 1 ci += 1 res -= 1 # Driver Code n = 4 k = 2 row = [ 1, 2 ] col = [ 4, 2 ] # Function call findCountRooks(row, col, n, k) # This code is contributed by sanjoy_62
C#
// C# implementation to find
// count of placing non-attacking
// rooks on the N x N chessboard
using System;
class P2Placerooks{
// Function to find the count of
// placing non-attacking rooks
// on the N x N chessboard
static void findCountRooks(int []row,
int []col,
int n, int k)
{
// Count of the Non-attacking rooks
int res = n - k;
Console.WriteLine(res + " ");
int ri = 0, ci = 0;
while (res-- > 0)
{
// Printing lexicographically
// smallest configuration
while (ri < k && row[ri] == 1)
{
ri++;
}
while (ci < k && col[ci] == 1)
{
ci++;
}
Console.WriteLine((ri + 1) + " " +
(ci + 1) + " ");
ri++;
ci++;
}
}
// Driver Code
public static void Main(String[] args)
{
int n = 4;
int k = 2;
int []row = { 1, 2 };
int []col = { 4, 2 };
// Function call
findCountRooks(row, col, n, k);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation to find
// count of placing non-attacking
// rooks on the N x N chessboard
// Function to find the count of
// placing non-attacking rooks
// on the N x N chessboard
function findCountRooks(row,col,n,k)
{
// Count of the Non-attacking rooks
let res = n - k;
document.write(res + "<br>");
let ri = 0, ci = 0;
while (res-- > 0)
{
// Printing lexicographically
// smallest configuration
while (ri < k && row[ri] == 1)
{
ri++;
}
while (ci < k && col[ci] == 1)
{
ci++;
}
document.write((ri + 1) + " "
+ (ci + 1) + "<br>");
ri++;
ci++;
}
}
// Driver Code
let n = 4;
let k = 2;
let row = [ 1, 2 ];
let col = [ 4, 2 ];
// Function call
findCountRooks(row, col, n, k);
</script>
2 2 1 3 2
Análisis de rendimiento:
- Complejidad de tiempo: O(N)
- Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Anmolbansal1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA