Un patrón móvil es una cuadrícula de celdas 3X3, donde dibujar un patrón específico (conectando una secuencia específica de celdas en orden) desbloqueará el móvil. En este problema, la tarea es calcular el número de formas de hacer el patrón de bloqueo con el número de conexiones en un rango dado. En términos generales, se nos da un rango como mínimo y máximo, necesitamos decir cuántos patrones se pueden hacer que usen al menos la celda de conexión mínima y la celda de conexión máxima como máximo.
Input : min = 5, max = 7 Output : 106080 Below are some example patterns
Una solución simple es hacer DFS simple pasando por varias conexiones desde todos los puntos de partida. Podemos optimizar viendo la simetría entre patrones, podemos tratar las celdas 1, 3, 7 y 9 como iguales. Del mismo modo, podemos tratar 2, 4, 6 y 8 como iguales. La respuesta devuelta por un miembro del mismo grupo se puede multiplicar por 4 para obtener el resultado de todos los miembros.
Lo siguiente a tener en cuenta es que los patrones a continuación no son válidos, porque no se permite saltar algunas celdas como en el diagrama a continuación, se saltan las celdas 8 y 5, 6.
Para encargarse de tales movimientos no válidos, se toma una array de salto 2D en el código siguiente que almacena posibles celdas de salto en la array de salto. Cuando llamamos de forma recursiva, imponemos una condición adicional de que si nos estamos moviendo de una celda a otra, lo que involucra alguna celda de salto, entonces esta celda ya debe visitarse para ignorar los movimientos no válidos.
En el siguiente código, hemos realizado llamadas recursivas de 1, 2 y 5 solo porque 1 cubrirá 3, 5 y 7 y 2 cubrirá 4, 6 y 8 debido a la simetría.
Vea el siguiente código para una mejor comprensión:
C++
// C/C++ program to find number of ways to lock the mobile
// pattern
#include <bits/stdc++.h>
using namespace std;
#define DOTS 10
// method to find total pattern starting from current cell
int totalPatternFromCur(bool visit[DOTS], int jump[DOTS][DOTS],
int cur, int toTouch)
{
if (toTouch <= 0)
{
// if last cell then return 1 way
return (toTouch == 0)? 1 : 0;
}
int ways = 0;
// make this cell visited before going to next call
visit[cur] = true;
for (int i=1; i<DOTS; i++)
{
/* if this cell is not visit AND
either i and cur are adjacent (then jump[i][cur] = 0)
or between cell must be visit already (
then visit[jump[i][cur]] = 1) */
if (!visit[i] && (!jump[i][cur] || visit[jump[i][cur]]))
ways += totalPatternFromCur(visit, jump, i, toTouch - 1);
}
// make this cell not visited after returning from call
visit[cur] = false;
return ways;
}
// method returns number of pattern with minimum m connection
// and maximum n connection
int waysOfConnection(int m, int n)
{
int jump[DOTS][DOTS] = {0};
// 2 lies between 1 and 3
jump[1][3] = jump[3][1] = 2;
// 8 lies between 7 and 9
jump[7][9] = jump[9][7] = 8;
// 4 lies between 1 and 7
jump[1][7] = jump[7][1] = 4;
// 6 lies between 3 and 9
jump[3][9] = jump[9][3] = 6;
// 5 lies between 1, 9 2, 8 3, 7 and 4, 6
jump[1][9] = jump[9][1] = jump[2][8] = jump[8][2]
= jump[3][7] = jump[7][3] = jump[4][6] = jump[6][4] = 5;
bool visit[DOTS] = {0};
int ways = 0;
for (int i = m; i <= n; i++)
{
// 1, 3, 7, 9 are symmetric so multiplying by 4
ways += 4 * totalPatternFromCur(visit, jump, 1, i - 1);
// 2, 4, 6, 8 are symmetric so multiplying by 4
ways += 4 * totalPatternFromCur(visit, jump, 2, i - 1);
ways += totalPatternFromCur(visit, jump, 5, i - 1);
}
return ways;
}
// Driver code to test above method
int main()
{
int minConnect = 4;
int maxConnect = 6;
cout << waysOfConnection(minConnect, maxConnect);
return 0;
}
Java
// Java program to find number of ways
// to lock the mobile pattern
class GFG
{
static int DOTS = 10;
// method to find total pattern starting from current cell
static int totalPatternFromCur(boolean visit[], int jump[][],
int cur, int toTouch)
{
if (toTouch <= 0)
{
// if last cell then return 1 way
return (toTouch == 0) ? 1 : 0;
}
int ways = 0;
// make this cell visited before
// going to next call
visit[cur] = true;
for (int i = 1; i < DOTS; i++)
{
/* if this cell is not visit AND
either i and cur are adjacent (then jump[i][cur] = 0)
or between cell must be visit already (
then visit[jump[i][cur]] = 1) */
if (!visit[i] && (jump[i][cur] == 0 ||
visit[jump[i][cur]]))
ways += totalPatternFromCur(visit, jump,
i, toTouch - 1);
}
// make this cell not visited
// after returning from call
visit[cur] = false;
return ways;
}
// method returns number of pattern with
// minimum m connection and maximum n connection
static int waysOfConnection(int m, int n)
{
int [][]jump = new int[DOTS][DOTS];
// 2 lies between 1 and 3
jump[1][3] = jump[3][1] = 2;
// 8 lies between 7 and 9
jump[7][9] = jump[9][7] = 8;
// 4 lies between 1 and 7
jump[1][7] = jump[7][1] = 4;
// 6 lies between 3 and 9
jump[3][9] = jump[9][3] = 6;
// 5 lies between 1, 9 2, 8 3, 7 and 4, 6
jump[1][9] = jump[9][1] = jump[2][8] =
jump[8][2] = jump[3][7] =
jump[7][3] = jump[4][6] =
jump[6][4] = 5;
boolean []visit = new boolean[DOTS];
int ways = 0;
for (int i = m; i <= n; i++)
{
// 1, 3, 7, 9 are symmetric so multiplying by 4
ways += 4 * totalPatternFromCur(visit,
jump, 1, i - 1);
// 2, 4, 6, 8 are symmetric so multiplying by 4
ways += 4 * totalPatternFromCur(visit,
jump, 2, i - 1);
ways += totalPatternFromCur(visit,
jump, 5, i - 1);
}
return ways;
}
// Driver Code
public static void main(String[] args)
{
int minConnect = 4;
int maxConnect = 6;
System.out.println(waysOfConnection(minConnect,
maxConnect));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find number of ways # to lock the mobile pattern DOTS = 10; # method to find total pattern starting from current cell def totalPatternFromCur(visit, jump, cur, toTouch): if (toTouch <= 0): # if last cell then return 1 way if (toTouch == 0): return 1; else: return 0; ways = 0; # make this cell visited before # going to next call visit[cur] = True; for i in range(1, DOTS): ''' * if this cell is not visit AND either i and cur are adjacent (then * jump[i][cur] = 0) or between cell must be visit already ( then * visit[jump[i][cur]] = 1) ''' if (visit[i] == False and (jump[i][cur] == 0 or visit[jump[i][cur]])): ways += totalPatternFromCur(visit, jump, i, toTouch - 1); # make this cell not visited # after returning from call visit[cur] = False; return ways; # method returns number of pattern with # minimum m connection and maximum n connection def waysOfConnection(m, n): jump = [[0 for i in range(DOTS)] for j in range(DOTS)]; # 2 lies between 1 and 3 jump[1][3] = jump[3][1] = 2; # 8 lies between 7 and 9 jump[7][9] = jump[9][7] = 8; # 4 lies between 1 and 7 jump[1][7] = jump[7][1] = 4; # 6 lies between 3 and 9 jump[3][9] = jump[9][3] = 6; # 5 lies between 1, 9 2, 8 3, 7 and 4, 6 jump[1][9] = jump[9][1] = jump[2][8] = jump[8][2] =\ jump[3][7] = jump[7][3] = jump[4][6] = jump[6][4] = 5; visit = [False]*DOTS; ways = 0; for i in range(m, n + 1): # 1, 3, 7, 9 are symmetric so multiplying by 4 ways += 4 * totalPatternFromCur(visit, jump, 1, i - 1); # 2, 4, 6, 8 are symmetric so multiplying by 4 ways += 4 * totalPatternFromCur(visit, jump, 2, i - 1); ways += totalPatternFromCur(visit, jump, 5, i - 1); return ways; # Driver Code if __name__ == '__main__': minConnect = 4; maxConnect = 6; print(waysOfConnection(minConnect, maxConnect)); # This code is contributed by 29AjayKumar
C#
// C# program to find number of ways
// to lock the mobile pattern
using System;
class GFG
{
static int DOTS = 10;
// method to find total pattern starting from current cell
static int totalPatternFromCur(Boolean []visit, int [,]jump,
int cur, int toTouch)
{
if (toTouch <= 0)
{
// if last cell then return 1 way
return (toTouch == 0) ? 1 : 0;
}
int ways = 0;
// make this cell visited before
// going to next call
visit[cur] = true;
for (int i = 1; i < DOTS; i++)
{
/* if this cell is not visit AND
either i and cur are adjacent (then jump[i,cur] = 0)
or between cell must be visit already (
then visit[jump[i,cur]] = 1) */
if (!visit[i] && (jump[i, cur] == 0 ||
visit[jump[i, cur]]))
ways += totalPatternFromCur(visit, jump,
i, toTouch - 1);
}
// make this cell not visited
// after returning from call
visit[cur] = false;
return ways;
}
// method returns number of pattern with
// minimum m connection and maximum n connection
static int waysOfConnection(int m, int n)
{
int [,]jump = new int[DOTS, DOTS];
// 2 lies between 1 and 3
jump[1, 3] = jump[3, 1] = 2;
// 8 lies between 7 and 9
jump[7, 9] = jump[9, 7] = 8;
// 4 lies between 1 and 7
jump[1, 7] = jump[7, 1] = 4;
// 6 lies between 3 and 9
jump[3, 9] = jump[9, 3] = 6;
// 5 lies between 1, 9 2, 8 3, 7 and 4, 6
jump[1, 9] = jump[9, 1] = jump[2, 8] =
jump[8, 2] = jump[3, 7] =
jump[7, 3] = jump[4, 6] =
jump[6, 4] = 5;
Boolean []visit = new Boolean[DOTS];
int ways = 0;
for (int i = m; i <= n; i++)
{
// 1, 3, 7, 9 are symmetric so multiplying by 4
ways += 4 * totalPatternFromCur(visit,
jump, 1, i - 1);
// 2, 4, 6, 8 are symmetric so multiplying by 4
ways += 4 * totalPatternFromCur(visit,
jump, 2, i - 1);
ways += totalPatternFromCur(visit,
jump, 5, i - 1);
}
return ways;
}
// Driver Code
public static void Main(String[] args)
{
int minConnect = 4;
int maxConnect = 6;
Console.WriteLine(waysOfConnection(minConnect,
maxConnect));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find number of ways
// to lock the mobile pattern
let DOTS = 10;
// method to find total pattern starting from current cell
function totalPatternFromCur(visit,jump,cur,toTouch)
{
if (toTouch <= 0)
{
// if last cell then return 1 way
return (toTouch == 0) ? 1 : 0;
}
let ways = 0;
// make this cell visited before
// going to next call
visit[cur] = true;
for (let i = 1; i < DOTS; i++)
{
/* if this cell is not visit AND
either i and cur are adjacent (then jump[i][cur] = 0)
or between cell must be visit already (
then visit[jump[i][cur]] = 1) */
if (!visit[i] && (jump[i][cur] == 0 ||
visit[jump[i][cur]]))
ways += totalPatternFromCur(visit, jump,
i, toTouch - 1);
}
// make this cell not visited
// after returning from call
visit[cur] = false;
return ways;
}
// method returns number of pattern with
// minimum m connection and maximum n connection
function waysOfConnection(m,n)
{
let jump = new Array(DOTS);
for(let i=0;i<DOTS;i++)
{
jump[i]=new Array(DOTS);
for(let j=0;j<DOTS;j++)
{
jump[i][j]=0;
}
}
// 2 lies between 1 and 3
jump[1][3] = jump[3][1] = 2;
// 8 lies between 7 and 9
jump[7][9] = jump[9][7] = 8;
// 4 lies between 1 and 7
jump[1][7] = jump[7][1] = 4;
// 6 lies between 3 and 9
jump[3][9] = jump[9][3] = 6;
// 5 lies between 1, 9 2, 8 3, 7 and 4, 6
jump[1][9] = jump[9][1] = jump[2][8] =
jump[8][2] = jump[3][7] =
jump[7][3] = jump[4][6] =
jump[6][4] = 5;
let visit = new Array(DOTS);
let ways = 0;
for (let i = m; i <= n; i++)
{
// 1, 3, 7, 9 are symmetric so multiplying by 4
ways += 4 * totalPatternFromCur(visit,
jump, 1, i - 1);
// 2, 4, 6, 8 are symmetric so multiplying by 4
ways += 4 * totalPatternFromCur(visit,
jump, 2, i - 1);
ways += totalPatternFromCur(visit,
jump, 5, i - 1);
}
return ways;
}
// Driver Code
let minConnect = 4;
let maxConnect = 6;
document.write(waysOfConnection(minConnect,
maxConnect));
// This code is contributed by rag2127
</script>
Producción:
34792
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA