Dado un tablero de ajedrez NXN . La tarea es verificar si el tablero de ajedrez dado es válido o no. Un tablero de ajedrez se considera válido si cada 2 celdas adyacentes están pintadas con un color diferente. Dos celdas se consideran adyacentes si comparten un límite.
El primer tablero de ajedrez es válido mientras que el segundo no es válido.
Ejemplos:
Input : N = 2
C = {
{ 1, 0 },
{ 0, 1 }
}
Output : Yes
Input : N = 2
C = {
{ 0, 0 },
{ 0, 0 }
}
Output : No
Observe, en un tablero de ajedrez, cada par de celdas adyacentes está pintada en un color diferente.
Entonces, para cada celda (i, j), verifique si las celdas adyacentes, es decir,
(i + 1, j), (i -1, j), (i, j + 1), (i, j – 1) están pintadas con color diferente a (i, j) o no.
Pseudocódigo:
int X[] = {0, -1, 0, 1};
int Y[] = {1, 0, -1, 0};
bool validateConfiguration(int M[N][N])
{
bool isValid = true;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < 4; k++)
{
int newX = i + X[k];
int newY = j + Y[k];
if (newX < N && newY < N && newX >= 0 &&
newY >= 0 && M[newX][newY] == M[i][j])
{
isValid = false;
}
}
}
}
return isValid;
}
A continuación se muestra la implementación de este enfoque:
C++
#include <bits/stdc++.h>
using namespace std;
#define MAX 2
// Check if the given chess board is valid or not.
bool isValid(int c[][MAX], int n)
{
int X[] = { 0, -1, 0, 1 };
int Y[] = { 1, 0, -1, 0 };
bool isValid = true;
// Traversing each cell of the chess board.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// for each adjacent cells
for (int k = 0; k < 4; k++) {
int newX = i + X[k];
int newY = j + Y[k];
// checking if they have different color
if (newX < n && newY < n && newX >= 0 &&
newY >= 0 && c[newX][newY] == c[i][j]) {
isValid = false;
}
}
}
}
return isValid;
}
// Driven Program
int main()
{
int n = 2;
int c[2][2] = { { 1, 0 },
{ 0, 1 } };
(isValid(c, n)) ? (cout << "Yes") : (cout << "No");
return 0;
}
Java
// Check if the given chess
// board is valid or not
class GFG
{
static int MAX = 2;
static boolean isValid(int c[][], int n)
{
int X[] = { 0, -1, 0, 1 };
int Y[] = { 1, 0, -1, 0 };
boolean isValid = true;
// Traversing each cell
// of the chess board.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// for each adjacent cells
for (int k = 0; k < 4; k++)
{
int newX = i + X[k];
int newY = j + Y[k];
// checking if they have
// different color
if (newX < n && newY < n &&
newX >= 0 && newY >= 0 &&
c[newX][newY] == c[i][j])
{
isValid = false;
}
}
}
}
return isValid;
}
// Driver Code
public static void main(String[] args)
{
int n = 2;
int[][] c = {{ 1, 0 },
{ 0, 1 }};
if (isValid(c, n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by ChitraNayal
Python 3
# Python 3 Program to Check
# if the given chessboard
# is valid or not
MAX = 2
# Check if the given chess
# board is valid or not.
def isValid(c, n) :
X = [ 0, -1, 0, 1]
Y = [ 1, 0, -1, 0]
isValid = True
# Traversing each cell
# of the chess board.
for i in range(n) :
for j in range(n) :
# for each adjacent cells
for k in range(n) :
newX = i + X[k]
newY = j + Y[k]
# checking if they have
# different color
if (newX < n and newY < n and
newX >= 0 and newY >= 0 and
c[newX][newY] == c[i][j]) :
isValid = false
return isValid
# Driver Code
if __name__ == "__main__" :
n = 2
c = [ [1, 0],
[0, 1] ]
if isValid(c, n) :
print("Yes")
else :
print("No")
# This code is contributed
# by ANKITRAI1
C#
// Check if the given chess
// board is valid or not.
using System;
class GFG
{
static bool isValid(int[,] c, int n)
{
int[] X = { 0, -1, 0, 1 };
int[] Y = { 1, 0, -1, 0 };
bool isValid = true;
// Traversing each cell
// of the chess board.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// for each adjacent cells
for (int k = 0; k < 4; k++)
{
int newX = i + X[k];
int newY = j + Y[k];
// checking if they have different color
if (newX < n && newY < n &&
newX >= 0 && newY >= 0 &&
c[newX, newY] == c[i, j])
{
isValid = false;
}
}
}
}
return isValid;
}
// Driver Code
public static void Main()
{
int n = 2;
int[,] c = {{ 1, 0 },
{ 0, 1 }};
if (isValid(c, n))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by ChitraNayal
PHP
<?php
// Check if the given chess
// board is valid or not.
function isValid(&$c, $n)
{
$X = array( 0, -1, 0, 1 );
$Y = array( 1, 0, -1, 0 );
$isValid = true;
// Traversing each cell
// of the chess board.
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
{
// for each adjacent cells
for ($k = 0; $k < 4; $k++)
{
$newX = $i + $X[$k];
$newY = $j + $Y[$k];
// checking if they have different color
if ($newX < $n && $newY < $n &&
$newX >= 0 && $newY >= 0 &&
$c[$newX][$newY] == $c[$i][$j])
{
$isValid = false;
}
}
}
}
return $isValid;
}
// Driver Code
$n = 2;
$c = array(array(1, 0),
array(0, 1));
echo (isValid($c, $n)) ? "Yes" : "No";
// This code is contributed by ChitraNayal
?>
Javascript
<script>
var MAX = 2;
// Check if the given chess
// board is valid or not.
function isValid(c, n)
{
var X = [ 0, -1, 0, 1 ];
var Y = [ 1, 0, -1, 0 ];
var isValid = true;
// Traversing each cell of the chess board.
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
// for each adjacent cells
for (var k = 0; k < 4; k++) {
var newX = i + X[k];
var newY = j + Y[k];
// checking if they have
// different color
if (newX < n && newY < n &&
newX >= 0 &&
newY >= 0 &&
c[newX][newY] == c[i][j]) {
isValid = false;
}
}
}
}
return isValid;
}
// Driven Program
var n = 2;
var c = [ [ 1, 0 ],
[ 0, 1 ] ];
(isValid(c, n)) ? (document.write( "Yes")) :
(document.write( "No"));
</script>
Producción :
Yes
Un enfoque más simple sería verificar si las celdas con sumas pares son del mismo color.
C++
#include <bits/stdc++.h>
using namespace std;
bool checkBoard(vector<vector<int>> board)
{
int base = board[0][0];
bool flag = true;
for(int i = 0; i < board.size(); i++)
{
for( int j = 0; j < board[i].size(); j++)
{
if(( i + j ) % 2 == 0)
{
if( board[i][j] != base )
{
return false;
}
}
else
{
if (board[i][j] == base)
{
return false;
}
}
}
}
return true;
}
int main()
{
vector<vector<int>> board1={{0, 1},
{1, 0}};
vector<vector<int>> board2={{1, 0, 1},
{0, 1, 0},
{1, 0, 1}};
vector<vector<int>> board3={{1, 0, 1},
{0, 1, 0},
{1, 1, 1}};
if(checkBoard(board1))
cout << "true\n";
else
cout << "false\n";
if(checkBoard(board2))
cout << "true\n";
else
cout << "false\n";
if(checkBoard(board3))
cout << "true\n";
else
cout << "false\n";
return 0;
}
//This code is contributed by aditya942003patil
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
static boolean checkBoard(int[][] board)
{
int base = board[0][0];
boolean flag = true;
for(int i = 0; i < board.length; i++)
{
for( int j = 0; j < board[i].length; j++)
{
if(( i + j ) % 2 == 0)
{
if( board[i][j] != base )
{
return false;
}
}
else
{
if (board[i][j] == base)
{
return false;
}
}
}
}
return true;
}
// Driver code
public static void main (String[] args) {
int[][] board1={{0, 1}, {1, 0}};
int[][] board2={{1, 0, 1},{0, 1, 0},{1, 0, 1}};
int[][] board3={{1, 0, 1},{0, 1, 0},{1, 1, 1}};
System.out.println(checkBoard(board1));
System.out.println(checkBoard(board2));
System.out.println(checkBoard(board3));
}
}
// This code is contributed by rag2127
Python3
# Write Python3 code here def checkBoard(board) : base = board[0][0] flag = True for i in range(len(board)) : for j in range(len(board[i])) : if( i + j ) % 2 == 0 : if board[i][j] != base : return False else : if board[i][j] == base : return False return True board1 = [[0, 1], [1, 0]] board2 = [[1, 0, 1], [0, 1, 0], [1, 0, 1]] board3 = [[1, 0, 1], [0, 1, 0], [1, 1, 1]] print(checkBoard(board1)) print(checkBoard(board2)) print(checkBoard(board3))
C#
using System;
public class GFG
{
static bool checkBoard(int[,] board)
{
int Base = board[0, 0];
for(int i = 0; i < board.GetLength(0); i++)
{
for( int j = 0; j < board.GetLength(1); j++)
{
if(( i + j ) % 2 == 0)
{
if( board[i, j] != Base )
{
return false;
}
}
else
{
if (board[i, j] == Base)
{
return false;
}
}
}
}
return true;
}
// Driver code
static public void Main ()
{
int[,] board1 = {{0, 1}, {1, 0}};
int[,] board2 = {{1, 0, 1},{0, 1, 0},{1, 0, 1}};
int[,] board3 = {{1, 0, 1},{0, 1, 0},{1, 1, 1}};
Console.WriteLine(checkBoard(board1));
Console.WriteLine(checkBoard(board2));
Console.WriteLine(checkBoard(board3));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
function checkBoard(board)
{
let base = board[0][0];
let flag = true;
for(let i = 0; i < board.length; i++)
{
for( let j = 0; j < board[i].length; j++)
{
if(( i + j ) % 2 == 0)
{
if( board[i][j] != base )
{
return false;
}
}
else
{
if (board[i][j] == base)
{
return false;
}
}
}
}
return true;
}
// Driver code
let board1 = [[0, 1], [1, 0]];
let board2 = [[1, 0, 1], [0, 1, 0], [1, 0, 1]];
let board3 = [[1, 0, 1], [0, 1, 0], [1, 1, 1]];
document.write(checkBoard(board1)+"<br>")
document.write(checkBoard(board2)+"<br>")
document.write(checkBoard(board3)+"<br>")
// This code is contributed by unknown2108
</script>
Producción
true true false