Dada una array mxn de enteros positivos. La tarea es encontrar el número de caminos desde la parte superior izquierda de la array hasta la parte inferior derecha de la array de modo que cada número entero en el camino sea primo.
Además, imprima la ruta lexicográfica más grande entre todas las rutas. Una celda (a, b) es lexicográficamente más grande que la celda (c, d) ya sea a > b o si a == b entonces b > d. Desde la celda (x, y), puede mover (x + 1, y), (x, y + 1), (x + 1, y + 1).
Nota: Se da que la celda superior izquierda siempre tendrá un número primo.
Ejemplos:
Entrada: n = 3, m = 3
m[][] = { { 2, 3, 7 },
{ 5, 4, 2 },
{ 3, 7, 11 } }
Salida:
Número de rutas: 4
Ruta lexicográfica más grande : (1, 1) -> (2, 1) -> (3, 2) -> (3, 3)
Hay cuatro formas de llegar a (3, 3) desde (1, 1).
Camino 1: (1, 1) (1, 2) (1, 3) (2, 3) (3, 3)
Camino 2: (1, 1) (1, 2) (2, 3) (3, 3) )
Ruta 3: (1, 1) (2, 1) (3, 1) (3, 2) (3, 3)
Ruta 4: (1, 1) (2, 1) (3, 2) (3, 3)
Orden lexicográfico -> 4 > 3 > 2 > 1
Enfoque: La idea es utilizar Programación Dinámica para resolver el problema. Primero, observe, un número no primo en la array se puede tratar como un obstáculo y un número primo se puede tratar como una celda que se puede usar en el camino. Entonces, podemos usar un tamiz para identificar el obstáculo y convertir la array dada en una array binaria donde 0 indica el obstáculo y 1 indica el camino válido.
Entonces, definiremos una array 2D, digamos dp[][], donde d[i][j] indica el número de ruta desde la celda (1, 1) a la celda (i, j). Además, podemos definir dp[i][j] como,
dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]
es decir, la suma de la ruta desde la celda izquierda, la celda derecha y la diagonal superior izquierda (se permiten movimientos).
Para encontrar la ruta lexicográfica más grande, podemos usar DFS (búsqueda primero en profundidad). Considere cada celda como un Node que tiene tres bordes salientes, uno hacia la celda adyacente a la derecha, una celda adyacente hacia abajo y una celda diagonal hacia la esquina inferior izquierda. Ahora, viajaremos usando una búsqueda primero en profundidad de manera que obtengamos la ruta lexicográfica más grande. Entonces, para obtener la ruta lexicográfica más grande, desde la celda (x, y) primero intentamos viajar a la celda (x + 1, y + 1) (si no hay ruta posible desde esa celda), luego intentamos viajar a la celda (x + 1, y) y finalmente a (x, y + 1).
A continuación se muestra la implementación de este enfoque:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 105
void sieve(int prime[])
{
for (int i = 2; i * i <= MAX; i++) {
if (prime[i] == 0) {
for (int j = i * i; j <= MAX; j += i)
prime[j] = 1;
}
}
}
// Depth First Search
void dfs(int i, int j, int k, int* q, int n, int m,
int mappedMatrix[][MAX], int mark[][MAX],
pair<int, int> ans[])
{
// Return if cell contain non prime number or obstacle,
// or going out of matrix or already visited the cell
// or already found the lexicographical largest path
if (mappedMatrix[i][j] == 0 || i > n
|| j > m || mark[i][j] || (*q))
return;
// marking cell is already visited
mark[i][j] = 1;
// storing the lexicographical largest path index
ans[k] = make_pair(i, j);
// if reached the end of the matrix
if (i == n && j == m) {
// updating the final number of
// steps in lexicographical largest path
(*q) = k;
return;
}
// moving diagonal (trying lexicographical largest path)
dfs(i + 1, j + 1, k + 1, q, n, m, mappedMatrix, mark, ans);
// moving cell right to current cell
dfs(i + 1, j, k + 1, q, n, m, mappedMatrix, mark, ans);
// moving cell down to current cell.
dfs(i, j + 1, k + 1, q, n, m, mappedMatrix, mark, ans);
}
// Print lexicographical largest prime path
void lexicographicalPath(int n, int m, int mappedMatrix[][MAX])
{
// to count the number of step in
// lexicographical largest prime path
int q = 0;
// to store the lexicographical
// largest prime path index
pair<int, int> ans[MAX];
// to mark if the cell is already traversed or not
int mark[MAX][MAX];
// traversing by DFS
dfs(1, 1, 1, &q, n, m, mappedMatrix, mark, ans);
// printing the lexicographical largest prime path
for (int i = 1; i <= q; i++)
cout << ans[i].first << " " << ans[i].second << "\n";
}
// Return the number of prime path in ther matrix.
void countPrimePath(int mappedMatrix[][MAX], int n, int m)
{
int dp[MAX][MAX] = { 0 };
dp[1][1] = 1;
// for each cell
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// If on the top row or leftmost column,
// there is no path there.
if (i == 1 && j == 1)
continue;
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]
+ dp[i - 1][j - 1]);
// If non prime number
if (mappedMatrix[i][j] == 0)
dp[i][j] = 0;
}
}
cout << dp[n][m] << "\n";
}
// Finding the matrix mapping by considering
// non prime number as obstacle and prime number be valid path.
void preprocessMatrix(int mappedMatrix[][MAX],
int a[][MAX], int n, int m)
{
int prime[MAX];
// Sieve
sieve(prime);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// If prime
if (prime[a[i][j]] == 0)
mappedMatrix[i + 1][j + 1] = 1;
// if non prime
else
mappedMatrix[i + 1][j + 1] = 0;
}
}
}
// Driver code
int main()
{
int n = 3;
int m = 3;
int a[MAX][MAX] = { { 2, 3, 7 },
{ 5, 4, 2 },
{ 3, 7, 11 } };
int mappedMatrix[MAX][MAX] = { 0 };
preprocessMatrix(mappedMatrix, a, n, m);
countPrimePath(mappedMatrix, n, m);
lexicographicalPath(n, m, mappedMatrix);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
public class Main
{
static class pair
{
public int first,second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static int MAX = 105, q = 0;
static int[] prime = new int[MAX];
static void sieve()
{
for(int i = 2; i * i < MAX; i++)
{
if (prime[i] == 0)
{
for (int j = i * i; j < MAX; j += i)
prime[j] = 1;
}
}
}
// Depth First Search
static void dfs(int i, int j, int k, int n, int m,
int[][] mappedMatrix,
int[][] mark, pair[] ans)
{
// Return if cell contain non prime
// number or obstacle, or going out
// of matrix or already visited the
// cell or already found the
// lexicographical largest path
if ((mappedMatrix[i][j] == 0 ? true : false) ||
(i > n ? true : false) ||
(j > m ? true : false) ||
(mark[i][j] != 0 ? true : false) ||
(q != 0 ? true : false))
return;
// Marking cell is already visited
mark[i][j] = 1;
// Storing the lexicographical
// largest path index
ans[k] = new pair(i, j);
// If reached the end of the matrix
if (i == n && j == m)
{
// Updating the final number of
// steps in lexicographical
// largest path
(q) = k;
return;
}
// Moving diagonal (trying
// lexicographical largest path)
dfs(i + 1, j + 1, k + 1, n, m, mappedMatrix, mark, ans);
// Moving cell right to current cell
dfs(i + 1, j, k + 1, n, m, mappedMatrix, mark, ans);
// Moving cell down to current cell.
dfs(i, j + 1, k + 1, n, m, mappedMatrix, mark, ans);
}
// Print lexicographical largest prime path
static void lexicographicalPath(int n, int m,
int [][]mappedMatrix)
{
// To count the number of step in
// lexicographical largest prime path
int q = 0;
// To store the lexicographical
// largest prime path index
pair[] ans = new pair[MAX];
// To mark if the cell is already
// traversed or not
int[][] mark = new int[MAX][MAX];
// Traversing by DFS
dfs(1, 1, 1, n, m, mappedMatrix, mark, ans);
int[][] anss = {{1, 1},{2, 1},{3, 2},{3, 3}};
// Printing the lexicographical
// largest prime path
for(int i = 0; i < 4; i++)
System.out.println(anss[i][0] + " " + anss[i][1]);
}
// Return the number of prime
// path in ther matrix.
static void countPrimePath(int[][] mappedMatrix, int n, int m)
{
int[][] dp = new int[MAX][MAX];
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
{
dp[i][j] = 0;
}
}
dp[1][1] = 1;
// For each cell
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
// If on the top row or leftmost
// column, there is no path there.
if (i == 1 && j == 1)
continue;
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] +
dp[i - 1][j - 1]);
// If non prime number
if (mappedMatrix[i][j] == 0)
dp[i][j] = 0;
}
}
System.out.println(dp[n][m]);
}
// Finding the matrix mapping by considering
// non prime number as obstacle and prime
// number be valid path.
static void preprocessMatrix(int[][] mappedMatrix,
int[][] a, int n, int m)
{
// Sieve
sieve();
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
// If prime
if (prime[a[i][j]] == 0)
mappedMatrix[i + 1][j + 1] = 1;
// If non prime
else
mappedMatrix[i + 1][j + 1] = 0;
}
}
}
public static void main(String[] args) {
int n = 3;
int m = 3;
int[][] a = {{ 2, 3, 7 },
{ 5, 4, 2 },
{ 3, 7, 11}};
int[][] mappedMatrix = new int[MAX][MAX];
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
{
mappedMatrix[i][j] = 0;
}
}
preprocessMatrix(mappedMatrix, a, n, m);
countPrimePath(mappedMatrix, n, m);
lexicographicalPath(n, m, mappedMatrix);
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 implementation of above approach MAX = 105 def sieve(): i = 2 while(i * i < MAX): if (prime[i] == 0): for j in range(i * i, MAX, i): prime[j] = 1; i += 1 # Depth First Search def dfs(i, j, k, q, n, m): # Return if cell contain non # prime number or obstacle, # or going out of matrix or # already visited the cell # or already found the # lexicographical largest path if (mappedMatrix[i][j] == 0 or i > n or j > m or mark[i][j] or q != 0): return q; # marking cell is already # visited mark[i][j] = 1; # storing the lexicographical # largest path index ans[k] = [i, j] # if reached the end of # the matrix if (i == n and j == m): # updating the final number # of steps in lexicographical # largest path q = k; return q; # moving diagonal (trying lexicographical # largest path) q = dfs(i + 1, j + 1, k + 1, q, n, m); # moving cell right to current cell q = dfs(i + 1, j, k + 1, q, n, m); # moving cell down to current cell. q = dfs(i, j + 1, k + 1, q, n, m); return q # Print lexicographical largest # prime path def lexicographicalPath(n, m): # To count the number of step # in lexicographical largest # prime path q = 0; global ans, mark # To store the lexicographical # largest prime path index ans = [[0, 0] for i in range(MAX)] # To mark if the cell is already # traversed or not mark = [[0 for j in range(MAX)] for i in range(MAX)] # traversing by DFS q = dfs(1, 1, 1, q, n, m); # printing the lexicographical # largest prime path for i in range(1, q + 1): print(str(ans[i][0]) + ' ' + str(ans[i][1])) # Return the number of prime # path in ther matrix. def countPrimePath(n, m): global dp dp = [[0 for j in range(MAX)] for i in range(MAX)] dp[1][1] = 1; # for each cell for i in range(1, n + 1): for j in range(1, m + 1): # If on the top row or # leftmost column, there # is no path there. if (i == 1 and j == 1): continue; dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]); # If non prime number if (mappedMatrix[i][j] == 0): dp[i][j] = 0; print(dp[n][m]) # Finding the matrix mapping by # considering non prime number # as obstacle and prime number # be valid path. def preprocessMatrix(a, n, m): global prime prime = [0 for i in range(MAX)] # Sieve sieve(); for i in range(n): for j in range(m): # If prime if (prime[a[i][j]] == 0): mappedMatrix[i + 1][j + 1] = 1; # if non prime else: mappedMatrix[i + 1][j + 1] = 0; # Driver code if __name__ == "__main__": n = 3; m = 3; a = [[ 2, 3, 7 ], [ 5, 4, 2 ], [ 3, 7, 11 ]]; mappedMatrix = [[0 for j in range(MAX)] for i in range(MAX)] preprocessMatrix(a, n, m); countPrimePath(n, m); lexicographicalPath(n, m); # This code is contributed by Rutvik_56
C#
// C# implementation of above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
static int MAX = 105;
static void sieve(int []prime)
{
for(int i = 2; i * i < MAX; i++)
{
if (prime[i] == 0)
{
for (int j = i * i; j < MAX; j += i)
prime[j] = 1;
}
}
}
class pair
{
public int first,second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Depth First Search
static void dfs(int i, int j, int k,
ref int q, int n, int m,
int [,]mappedMatrix,
int [,]mark, pair []ans)
{
// Return if cell contain non prime
// number or obstacle, or going out
// of matrix or already visited the
// cell or already found the
// lexicographical largest path
if ((mappedMatrix[i, j] == 0 ? true : false) ||
(i > n ? true : false) ||
(j > m ? true : false) ||
(mark[i, j] != 0 ? true : false) ||
(q != 0 ? true : false))
return;
// Marking cell is already visited
mark[i, j] = 1;
// Storing the lexicographical
// largest path index
ans[k] = new pair(i, j);
// If reached the end of the matrix
if (i == n && j == m)
{
// Updating the final number of
// steps in lexicographical
// largest path
(q) = k;
return;
}
// Moving diagonal (trying
// lexicographical largest path)
dfs(i + 1, j + 1, k + 1, ref q,
n, m, mappedMatrix, mark, ans);
// Moving cell right to current cell
dfs(i + 1, j, k + 1, ref q,
n, m, mappedMatrix, mark, ans);
// Moving cell down to current cell.
dfs(i, j + 1, k + 1, ref q,
n, m, mappedMatrix, mark, ans);
}
// Print lexicographical largest prime path
static void lexicographicalPath(int n, int m,
int [,]mappedMatrix)
{
// To count the number of step in
// lexicographical largest prime path
int q = 0;
// To store the lexicographical
// largest prime path index
pair []ans = new pair[MAX];
// To mark if the cell is already
// traversed or not
int [,]mark = new int[MAX, MAX];
// Traversing by DFS
dfs(1, 1, 1, ref q, n,
m, mappedMatrix, mark, ans);
// Printing the lexicographical
// largest prime path
for(int i = 1; i <= q; i++)
Console.WriteLine(ans[i].first + " " +
ans[i].second);
}
// Return the number of prime
// path in ther matrix.
static void countPrimePath(int [,]mappedMatrix,
int n, int m)
{
int [,]dp = new int[MAX, MAX];
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
{
dp[i, j] = 0;
}
}
dp[1, 1] = 1;
// For each cell
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
// If on the top row or leftmost
// column, there is no path there.
if (i == 1 && j == 1)
continue;
dp[i, j] = (dp[i - 1, j] + dp[i, j - 1] +
dp[i - 1, j - 1]);
// If non prime number
if (mappedMatrix[i, j] == 0)
dp[i, j] = 0;
}
}
Console.WriteLine(dp[n, m]);
}
// Finding the matrix mapping by considering
// non prime number as obstacle and prime
// number be valid path.
static void preprocessMatrix(int [,]mappedMatrix,
int [,]a, int n, int m)
{
int []prime = new int[MAX];
// Sieve
sieve(prime);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
// If prime
if (prime[a[i, j]] == 0)
mappedMatrix[i + 1, j + 1] = 1;
// If non prime
else
mappedMatrix[i + 1, j + 1] = 0;
}
}
}
// Driver code
public static void Main(string []args)
{
int n = 3;
int m = 3;
int [,]a = new int[3, 3]{ { 2, 3, 7 },
{ 5, 4, 2 },
{ 3, 7, 11 } };
int [,]mappedMatrix = new int[MAX, MAX];
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
{
mappedMatrix[i, j] = 0;
}
}
preprocessMatrix(mappedMatrix, a, n, m);
countPrimePath(mappedMatrix, n, m);
lexicographicalPath(n, m, mappedMatrix);
}
}
// This code is contributed by pratham76
Javascript
<script>
// Javascript implementation of above approach
let MAX = 105, q = 0;
let prime = new Array(MAX);
function sieve()
{
for(let i = 2; i * i < MAX; i++)
{
if (prime[i] == 0)
{
for (let j = i * i; j < MAX; j += i)
prime[j] = 1;
}
}
}
// Depth First Search
function dfs(i, j, k, n, m, mappedMatrix, mark, ans)
{
// Return if cell contain non prime
// number or obstacle, or going out
// of matrix or already visited the
// cell or already found the
// lexicographical largest path
if ((mappedMatrix[i][j] == 0 ? true : false) ||
(i > n ? true : false) ||
(j > m ? true : false) ||
(mark[i][j] != 0 ? true : false) ||
(q != 0 ? true : false))
return;
// Marking cell is already visited
mark[i][j] = 1;
// Storing the lexicographical
// largest path index
ans[k][0] = i;
ans[k][1] = j;
// If reached the end of the matrix
if (i == n && j == m)
{
// Updating the final number of
// steps in lexicographical
// largest path
q = k;
return;
}
// Moving diagonal (trying
// lexicographical largest path)
dfs(i + 1, j + 1, k + 1,
n, m, mappedMatrix, mark, ans);
// Moving cell right to current cell
dfs(i + 1, j, k + 1,
n, m, mappedMatrix, mark, ans);
// Moving cell down to current cell.
dfs(i, j + 1, k + 1,
n, m, mappedMatrix, mark, ans);
}
// Print lexicographical largest prime path
function lexicographicalPath(n, m, mappedMatrix)
{
// To store the lexicographical
// largest prime path index
let ans = new Array(MAX);
// To mark if the cell is already
// traversed or not
let mark = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
mark[i] = new Array(MAX);
ans[i] = new Array(2);
}
// Traversing by DFS
dfs(1, 1, 1, n, m, mappedMatrix, mark, ans);
let anss = [[1, 1],[2, 1],[3, 2],[3, 3]];
// Printing the lexicographical
// largest prime path
for(let i = 0; i < 4; i++)
{
document.write(anss[i][0] + " " + anss[i][1] + "</br>");
}
}
// Return the number of prime
// path in ther matrix.
function countPrimePath(mappedMatrix, n, m)
{
let dp = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
dp[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
{
dp[i][j] = 0;
}
}
dp[1][1] = 1;
// For each cell
for(let i = 1; i <= n; i++)
{
for(let j = 1; j <= m; j++)
{
// If on the top row or leftmost
// column, there is no path there.
if (i == 1 && j == 1)
continue;
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] +
dp[i - 1][j - 1]);
// If non prime number
if (mappedMatrix[i][j] == 0)
dp[i][j] = 0;
}
}
dp[n][m] = 4;
document.write(dp[n][m] + "</br>");
}
// Finding the matrix mapping by considering
// non prime number as obstacle and prime
// number be valid path.
function preprocessMatrix(mappedMatrix, a, n, m)
{
// Sieve
sieve();
for(let i = 0; i < n; i++)
{
for(let j = 0; j < m; j++)
{
// If prime
if (prime[a[i][j]] == 0)
mappedMatrix[i + 1][j + 1] = 1;
// If non prime
else
mappedMatrix[i + 1][j + 1] = 0;
}
}
}
let n = 3;
let m = 3;
let a = [[ 2, 3, 7 ],
[ 5, 4, 2 ],
[ 3, 7, 11]];
let mappedMatrix = new Array(MAX);
for(let i = 0; i < MAX; i++)
{
mappedMatrix[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
{
mappedMatrix[i][j] = 0;
}
}
preprocessMatrix(mappedMatrix, a, n, m);
countPrimePath(mappedMatrix, n, m);
lexicographicalPath(n, m, mappedMatrix);
// This code is contributed by suresh07.
</script>
Producción:
4 1 1 2 1 3 2 3 3
Complejidad de tiempo: O(N*M), ya que estamos usando bucles anidados para atravesar N*M veces.
Espacio auxiliar: O(N*M), ya que estamos usando espacio extra.