Dado un número entero N tal que hay un tablero de ajedrez de tamaño N*N y una array pos[][] de K pares de números enteros que representan las posiciones de las torres colocadas en el tablero de ajedrez dado. La tarea es encontrar el número máximo de torres con sus posiciones que se pueden colocar en el tablero de ajedrez dado de manera que ninguna torre ataque a otra torre. Imprime las posiciones en orden lexicográfico.
Ejemplos:
Entrada: N = 4, K = 2, pos[][] = {{1, 4}, {2, 2}}
Salida:
2
3 1
4 3
Explicación:
Solo se pueden colocar 2 torres más en el tablero dado y sus posiciones son (3, 1) y (4, 3).
Entrada: N = 5, K = 0, pos[][] = {}
Salida:
5
1 1
2 2
3 3
4 4
5 5
Explicación:
Dado que el tablero de ajedrez está vacío, podemos colocar 5 torres en el tablero dado y sus posiciones son (1, 1), (2, 2), (3, 3), (4, 4) y (5, 5).
Enfoque Ingenuo: El enfoque más simple es tratar de colocar una torre en cada posición vacía del tablero de ajedrez y verificar si ataca las torres ya colocadas o no. A continuación se muestran los pasos:
- Inicialice una array 2D M[][] de tamaño N*N para representar el tablero de ajedrez y coloque las torres ya dadas en él.
- Atraviese la array completa M[][] y verifique si la i-ésima fila y la j-ésima columna contienen alguna torre
- Si la i-ésima fila y la j-ésima columna no contienen ninguna torre, entonces se coloca una torre allí y esta celda se agrega al resultado.
- De lo contrario, muévase a la siguiente celda vacía en el tablero de ajedrez.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: el enfoque se basa en la idea de que se puede colocar un máximo de (N – K) torres en el tablero de ajedrez de acuerdo con el Principio del casillero . A continuación se muestran los pasos:
- Dado que dos de las torres dadas no se atacan entre sí, todas las filas dadas en la entrada deben ser únicas. De manera similar, todas las columnas dadas en la entrada deben ser únicas.
- Por lo tanto, coloque las torres solo en N – K filas no utilizadas y N – K columnas no utilizadas.
- Por lo tanto, la configuración lexicográficamente mínima 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.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the maximum rooks
// and their positions
void countRooks(int n, int k,
int pos[2][2])
{
int row[n] = {0};
int col[n] = {0};
// Initialize row and col array
for (int i = 0; i < n; i++)
{
row[i] = 0;
col[i] = 0;
}
// Marking the location of
// already placed rooks
for (int i = 0; i < k; i++)
{
row[pos[i][0] - 1] = 1;
col[pos[i][1] - 1] = 1;
}
int res = n - k;
// Print number of non-attacking
// rooks that can be placed
cout << res << " " << endl;
// To store the placed rook
// location
int ri = 0, ci = 0;
while (res-- > 0)
{
// Print lexicographically
// smallest order
while (row[ri] == 1)
{
ri++;
}
while (col[ci] == 1)
{
ci++;
}
cout << (ri + 1) << " " <<
(ci + 1) << " " <<endl;
ri++;
ci++;
}
}
// Driver Code
int main()
{
// Size of board
int N = 4;
// Number of rooks already placed
int K = 2;
// Position of rooks
int pos[2][2] = {{1, 4}, {2, 2}};
// Function call
countRooks(N, K, pos);
}
// This code is contributed by shikhasingrajput
Java
// Java program for the above approach
public class GFG {
// Function to print the maximum rooks
// and their positions
private static void countRooks(int n, int k,
int pos[][])
{
int row[] = new int[n];
int col[] = new int[n];
// Initialize row and col array
for (int i = 0; i < n; i++) {
row[i] = 0;
col[i] = 0;
}
// Marking the location of
// already placed rooks
for (int i = 0; i < k; i++) {
row[pos[i][0] - 1] = 1;
col[pos[i][1] - 1] = 1;
}
int res = n - k;
// Print number of non-attacking
// rooks that can be placed
System.out.println(res + " ");
// To store the placed rook
// location
int ri = 0, ci = 0;
while (res-- > 0) {
// Print lexicographically
// smallest order
while (row[ri] == 1) {
ri++;
}
while (col[ci] == 1) {
ci++;
}
System.out.println(
(ri + 1)
+ " " + (ci + 1)
+ " ");
ri++;
ci++;
}
}
// Driver Code
public static void main(String[] args)
{
// Size of board
int N = 4;
// Number of rooks already placed
int K = 2;
// Position of rooks
int pos[][] = { { 1, 4 }, { 2, 2 } };
// Function call
countRooks(N, K, pos);
}
}
Python3
# Python3 program for the above approach # Function to print maximum rooks # and their positions def countRooks(n, k, pos): row = [0 for i in range(n)] col = [0 for i in range(n)] # Marking the location of # already placed rooks for i in range(k): row[pos[i][0] - 1] = 1 col[pos[i][1] - 1] = 1 res = n - k # Print number of non-attacking # rooks that can be placed print(res) # To store the placed rook # location ri = 0 ci = 0 while (res > 0): # Print lexicographically # smallest order while (row[ri] == 1): ri += 1 while (col[ci] == 1): ci += 1 print((ri + 1), (ci + 1)) ri += 1 ci += 1 res -= 1 # Driver Code if __name__ == '__main__': # Size of board N = 4 # Number of rooks already placed K = 2 # Position of rooks pos= [ [ 1, 4 ], [ 2, 2 ] ] # Function call countRooks(N, K, pos) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to print the maximum rooks
// and their positions
private static void countRooks(int n, int k,
int [, ]pos)
{
int []row = new int[n];
int []col = new int[n];
// Initialize row and col array
for (int i = 0; i < n; i++)
{
row[i] = 0;
col[i] = 0;
}
// Marking the location of
// already placed rooks
for (int i = 0; i < k; i++)
{
row[pos[i, 0] - 1] = 1;
col[pos[i, 1] - 1] = 1;
}
int res = n - k;
// Print number of non-attacking
// rooks that can be placed
Console.WriteLine(res + " ");
// To store the placed rook
// location
int ri = 0, ci = 0;
while (res -- > 0)
{
// Print lexicographically
// smallest order
while (row[ri] == 1)
{
ri++;
}
while (col[ci] == 1)
{
ci++;
}
Console.WriteLine((ri + 1) + " " +
(ci + 1) + " ");
ri++;
ci++;
}
}
// Driver Code
public static void Main(String[] args)
{
// Size of board
int N = 4;
// Number of rooks already placed
int K = 2;
// Position of rooks
int [, ]pos = {{1, 4}, {2, 2}};
// Function call
countRooks(N, K, pos);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to print the maximum rooks
// and their positions
function countRooks(n, k, pos)
{
let row = new Array(n).fill(0);
let col = new Array(n).fill(0);
// Initialize row and col array
for (let i = 0; i < n; i++) {
row[i] = 0;
col[i] = 0;
}
// Marking the location of
// already placed rooks
for (let i = 0; i < k; i++) {
row[pos[i][0] - 1] = 1;
col[pos[i][1] - 1] = 1;
}
let res = n - k;
// Print number of non-attacking
// rooks that can be placed
document.write(res + " " + "<br/>");
// To store the placed rook
// location
let ri = 0, ci = 0;
while (res-- > 0) {
// Print lexicographically
// smallest order
while (row[ri] == 1) {
ri++;
}
while (col[ci] == 1) {
ci++;
}
document.write(
(ri + 1)
+ " " + (ci + 1)
+ " " + "<br/>");
ri++;
ci++;
}
}
// Driver Code
// Size of board
let N = 4;
// Number of rooks already placed
let K = 2;
// Position of rooks
let pos = [[ 1, 4 ], [ 2, 2 ]];
// Function call
countRooks(N, K, pos);
</script>
2 3 1 4 3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por Anmolbansal1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA