Dado un tablero de ajedrez infinito con las mismas reglas que el del ajedrez. También se dan las coordenadas de N caballos en el tablero de ajedrez infinito (-10 ^ 9 <= x, y <= 10 ^ 9 ) y la coordenada del rey, la tarea es comprobar si el rey está en jaque mate o no.
Ejemplos:
Input: a[] = { {1, 0}, {0, 2}, {2, 5}, {4, 4}, {5, 0}, {6, 2} } king -> {3, 2}
Output: Yes
The king cannot make any move as it has been check mate.
Input: a[] = { {1, 1} } king -> {3, 4}
Output: No
The king can make valid moves.
Enfoque: El movimiento del caballo es inusual entre las piezas de ajedrez. Se mueve a un cuadrado que está a dos cuadrados de distancia horizontalmente y un cuadrado verticalmente, o dos cuadrados verticalmente y un cuadrado horizontalmente. El movimiento completo, por lo tanto, se parece a la letra «L» en todas las formas posibles (8 movimientos posibles). Por lo tanto, use un mapa hash de pares para marcar todas las coordenadas posibles donde el caballo puede moverse. Si el Rey no puede moverse a ninguna de sus 8 coordenadas cercanas, es decir, si la coordenada es rota por el movimiento de un caballo, entonces es un «jaque mate».
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for checking if a king
// can move a valid move or not when
// N nights are there in a modified chessboard
#include <bits/stdc++.h>
using namespace std;
bool checkCheckMate(pair<int, int> a[], int n, int kx, int ky)
{
// Pair of hash to mark the coordinates
map<pair<int, int>, int> mpp;
// iterate for Given N knights
for (int i = 0; i < n; i++) {
int x = a[i].first;
int y = a[i].second;
// mark all the "L" shaped coordinates
// that can be reached by a Knight
// initial position
mpp[{ x, y }] = 1;
// 1-st move
mpp[{ x - 2, y + 1 }] = 1;
// 2-nd move
mpp[{ x - 2, y - 1 }] = 1;
// 3-rd move
mpp[{ x + 1, y + 2 }] = 1;
// 4-th move
mpp[{ x + 1, y - 2 }] = 1;
// 5-th move
mpp[{ x - 1, y + 2 }] = 1;
// 6-th move
mpp[{ x + 2, y + 1 }] = 1;
// 7-th move
mpp[{ x + 2, y - 1 }] = 1;
// 8-th move
mpp[{ x - 1, y - 2 }] = 1;
}
// iterate for all possible 8 coordinates
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
int nx = kx + i;
int ny = ky + j;
if (i != 0 && j != 0) {
// check a move can be made or not
if (!mpp[{ nx, ny }]) {
return true;
}
}
}
}
// any moves
return false;
}
// Driver Code
int main()
{
pair<int, int> a[] = { { 1, 0 }, { 0, 2 }, { 2, 5 },
{ 4, 4 }, { 5, 0 }, { 6, 2 }};
int n = sizeof(a) / sizeof(a[0]);
int x = 3, y = 2;
if (checkCheckMate(a, n, x, y))
cout << "Not Checkmate!";
else
cout << "Yes its checkmate!";
return 0;
}
Java
// Java program for checking if a king
// can move a valid move or not when
// N nights are there in a modified chessboard
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static boolean checkCheckMate(pair a[], int n,
int kx, int ky)
{
// Pair of hash to mark the coordinates
HashMap<pair,
Integer> mpp = new HashMap<pair,
Integer>();
// iterate for Given N knights
for (int i = 0; i < n; i++)
{
int x = a[i].first;
int y = a[i].second;
// mark all the "L" shaped coordinates
// that can be reached by a Knight
// initial position
mpp.put(new pair( x, y ), 1);
// 1-st move
mpp.put(new pair( x - 2, y + 1 ), 1);
// 2-nd move
mpp.put(new pair( x - 2, y - 1 ), 1);
// 3-rd move
mpp.put(new pair( x + 1, y + 2 ), 1);
// 4-th move
mpp.put(new pair( x + 1, y - 2 ), 1);
// 5-th move
mpp.put(new pair( x - 1, y + 2 ), 1);
// 6-th move
mpp.put(new pair( x + 2, y + 1 ), 1);
// 7-th move
mpp.put(new pair( x + 2, y - 1 ), 1);
// 8-th move
mpp.put(new pair( x - 1, y - 2 ), 1);
}
// iterate for all possible 8 coordinates
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
int nx = kx + i;
int ny = ky + j;
if (i != 0 && j != 0)
{
// check a move can be made or not
pair p =new pair(nx, ny );
if (mpp.get(p) != null)
{
return true;
}
}
}
}
// any moves
return false;
}
// Driver Code
public static void main(String[] args)
{
pair a[] = {new pair( 1, 0 ), new pair( 0, 2 ),
new pair( 2, 5 ), new pair( 4, 4 ),
new pair( 5, 0 ), new pair( 6, 2 )};
int n = a.length;
int x = 3, y = 2;
if (checkCheckMate(a, n, x, y))
System.out.println("Not Checkmate!");
else
System.out.println("Yes its checkmate!");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program for checking if a king
# can move a valid move or not when
# N nights are there in a modified chessboard
def checkCheckMate(a, n, kx, ky):
# Pair of hash to mark the coordinates
mpp = {}
# iterate for Given N knights
for i in range(0, n):
x = a[i][0]
y = a[i][1]
# mark all the "L" shaped coordinates
# that can be reached by a Knight
# initial position
mpp[(x, y)] = 1
# 1-st move
mpp[(x - 2, y + 1)] = 1
# 2-nd move
mpp[(x - 2, y - 1)] = 1
# 3-rd move
mpp[(x + 1, y + 2)] = 1
# 4-th move
mpp[(x + 1, y - 2)] = 1
# 5-th move
mpp[(x - 1, y + 2)] = 1
# 6-th move
mpp[(x + 2, y + 1)] = 1
# 7-th move
mpp[(x + 2, y - 1)] = 1
# 8-th move
mpp[(x - 1, y - 2)] = 1
# iterate for all possible 8 coordinates
for i in range(-1, 2):
for j in range(-1, 2):
nx = kx + i
ny = ky + j
if i != 0 and j != 0:
# check a move can be made or not
if not mpp[(nx, ny)]:
return True
# any moves
return False
# Driver Code
if __name__ == "__main__":
a = [[1, 0], [0, 2], [2, 5],
[4, 4], [5, 0], [6, 2]]
n = len(a)
x, y = 3, 2
if checkCheckMate(a, n, x, y):
print("Not Checkmate!")
else:
print("Yes its checkmate!")
# This code is contributed by Rituraj Jain
C#
// C# program for checking if a king
// can move a valid move or not when
// N nights are there in a modified chessboard
using System;
using System.Collections.Generic;
class GFG
{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static bool checkCheckMate(pair []a, int n,
int kx, int ky)
{
// Pair of hash to mark the coordinates
Dictionary<pair,
int> mpp = new Dictionary<pair,
int>();
// iterate for Given N knights
for (int i = 0; i < n; i++)
{
int x = a[i].first;
int y = a[i].second;
// mark all the "L" shaped coordinates
// that can be reached by a Knight
// initial position
mpp.Add(new pair( x, y ), 1);
// 1-st move
mpp.Add(new pair( x - 2, y + 1 ), 1);
// 2-nd move
mpp.Add(new pair( x - 2, y - 1 ), 1);
// 3-rd move
mpp.Add(new pair( x + 1, y + 2 ), 1);
// 4-th move
mpp.Add(new pair( x + 1, y - 2 ), 1);
// 5-th move
mpp.Add(new pair( x - 1, y + 2 ), 1);
// 6-th move
mpp.Add(new pair( x + 2, y + 1 ), 1);
// 7-th move
mpp.Add(new pair( x + 2, y - 1 ), 1);
// 8-th move
mpp.Add(new pair( x - 1, y - 2 ), 1);
}
// iterate for all possible 8 coordinates
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
int nx = kx + i;
int ny = ky + j;
if (i != 0 && j != 0)
{
// check a move can be made or not
pair p = new pair(nx, ny);
if (mpp.ContainsKey(p))
{
return true;
}
}
}
}
// any moves
return false;
}
// Driver Code
public static void Main(String[] args)
{
pair []a = {new pair( 1, 0 ), new pair( 0, 2 ),
new pair( 2, 5 ), new pair( 4, 4 ),
new pair( 5, 0 ), new pair( 6, 2 )};
int n = a.Length;
int x = 3, y = 2;
if (checkCheckMate(a, n, x, y))
Console.WriteLine("Not Checkmate!");
else
Console.WriteLine("Yes its checkmate!");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program for checking if a king
// can move a valid move or not when
// N nights are there in a modified chessboard
class pair
{
constructor(first, second)
{
this.first = first;
this.second = second;
}
}
function checkCheckMate(a, n, kx, ky)
{
// Pair of hash to mark the coordinates
var mpp = new Map();
// iterate for Given N knights
for (var i = 0; i < n; i++)
{
var x = a[i].first;
var y = a[i].second;
// mark all the "L" shaped coordinates
// that can be reached by a Knight
// initial position
mpp.set(new pair( x, y ), 1);
// 1-st move
mpp.set(new pair( x - 2, y + 1 ), 1);
// 2-nd move
mpp.set(new pair( x - 2, y - 1 ), 1);
// 3-rd move
mpp.set(new pair( x + 1, y + 2 ), 1);
// 4-th move
mpp.set(new pair( x + 1, y - 2 ), 1);
// 5-th move
mpp.set(new pair( x - 1, y + 2 ), 1);
// 6-th move
mpp.set(new pair( x + 2, y + 1 ), 1);
// 7-th move
mpp.set(new pair( x + 2, y - 1 ), 1);
// 8-th move
mpp.set(new pair( x - 1, y - 2 ), 1);
}
// iterate for all possible 8 coordinates
for (var i = -1; i < 2; i++)
{
for (var j = -1; j < 2; j++)
{
var nx = kx + i;
var ny = ky + j;
if (i != 0 && j != 0)
{
// check a move can be made or not
var p = new pair(nx, ny);
if (mpp.has(p))
{
return true;
}
}
}
}
// any moves
return false;
}
// Driver Code
var a = [new pair( 1, 0 ), new pair( 0, 2 ),
new pair( 2, 5 ), new pair( 4, 4 ),
new pair( 5, 0 ), new pair( 6, 2 )];
var n = a.length;
var x = 3, y = 2;
if (checkCheckMate(a, n, x, y))
document.write("Not Checkmate!");
else
document.write("Yes its checkmate!");
</script>
Producción
Yes its checkmate!
Complejidad temporal: O(N).
Espacio Auxiliar: O(N)