Compruebe si el rompecabezas se puede resolver o no

Dado un rompecabezas especial que consta de N filas y M columnas, todas las piezas son idénticas. Cada pieza tiene tres pestañas y una en blanco. La tarea es verificar si el rompecabezas se puede resolver colocando las piezas de tal manera que la pestaña de una pieza encaje perfectamente en un espacio en blanco de otra pieza.

Nota : gira y traslada las piezas para resolver el rompecabezas. 

Ejemplos:

Entrada: N = 2, M = 2
Salida:

Entrada: N = 1, M = 3
Salida:
 

Enfoque: La observación clave en el problema es que:

  • Si el Rompecabezas tiene solo una fila o solo una columna. Entonces es posible resolver el rompecabezas colocando una pestaña en blanco en ese lado compartido.
  • Si el Rompecabezas tiene dos filas y dos columnas. Luego, el rompecabezas se puede resolver colocando las pestañas en blanco en una string circular.
  • De lo contrario, no es posible resolver el rompecabezas.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the jigsaw
// Puzzle is solveable or not
void checkSolveable(int n, int m)
{
   
    // Base Case
    if (n == 1 or m == 1)
        cout << "YES";
   
    // By placing the blank tabs
    // as a chain
    else if (m == 2 and n == 2)
        cout << "YES";
    else
        cout << "NO";
}
  
// Driver Code
int main()
{
    int n = 1, m = 3;
   
    checkSolveable(n, m);
}
 
// This code is contributed by jana_sayantan

Java

// Java program for the above approach
import java.util.*;
  
class GFG{
  
// Function to check if the jigsaw
// Puzzle is solveable or not
static void checkSolveable(int n, int m)
{
    
    // Base Case
    if (n == 1 || m == 1)
       System.out.print("YES");
    
    // By placing the blank tabs
    // as a chain
    else if (m == 2 && n == 2)
        System.out.print("YES");
    else
        System.out.print("NO");
}
 
// Driver Code
public static void main(String[] args)
{
     int n = 1, m = 3;
    
    checkSolveable(n, m);
}
}
 
// This code is contributed by sanjoy_62

Python

# Python program for the above approach
 
# Function to check if the jigsaw
# Puzzle is solveable or not
def checkSolveable(n, m):
 
    # Base Case
    if n == 1 or m == 1:
        print("YES")
         
    # By placing the blank tabs
    # as a chain
    elif m == 2 and n == 2:
        print("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == "__main__":
    n = 1
    m = 3
    checkSolveable(n, m)

C#

// C# program for the above approach
using System;
   
class GFG{
   
// Function to check if the jigsaw
// Puzzle is solveable or not
static void checkSolveable(int n, int m)
{
     
    // Base Case
    if (n == 1 || m == 1)
       Console.WriteLine("YES");
     
    // By placing the blank tabs
    // as a chain
    else if (m == 2 && n == 2)
        Console.WriteLine("YES");
    else
        Console.WriteLine("NO");
}
  
// Driver Code
public static void Main()
{
    int n = 1, m = 3;
   
    checkSolveable(n, m);
}
}
 
// This code is contributed by susmitakundugoaldanga

Javascript

<script>
 
// JavaScript implementation of the above approach
 
// Function to check if the jigsaw
// Puzzle is solveable or not
function checkSolveable(n, m)
{
     
    // Base Case
    if (n == 1 || m == 1)
       document.write("YES");
     
    // By placing the blank tabs
    // as a chain
    else if (m == 2 && n == 2)
        document.write("YES");
    else
        document.write("NO");
}
 
// Driver code
         
    let n = 1, m = 3;
     
    checkSolveable(n, m);
     
    // This code is contributed by code_hunt.
</script>
Producción: 

YES

 

Tiempo Complejidad: O(1) 
Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por harshdhiman725 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *