Dada una array que contiene solo caracteres alfabéticos inferiores, necesitamos contar el número de caminos palindrómicos en la array dada. Una ruta se define como una secuencia de celdas que comienza en la celda superior izquierda y termina en la celda inferior derecha . Solo podemos movernos hacia la derecha y hacia abajo desde la celda actual.
Ejemplos:
Input : mat[][] = {"aaab”,
"baaa”
“abba”}
Output : 3
Number of palindromic paths are 3 from top-left to
bottom-right.
aaaaaa (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) ->
(1, 3) -> (2, 3)
aaaaaa (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) ->
(1, 3) -> (2, 3)
abaaba (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) ->
(2, 2) -> (2, 3)
Podemos resolver este problema recursivamente, comenzamos desde dos esquinas de un camino palindrómico (arriba a la izquierda y abajo a la derecha). En cada llamada recursiva, mantenemos un estado que constituirá dos celdas, una desde el inicio y otra desde el final, que deben ser iguales para la propiedad del palíndromo. Si en un estado, ambos caracteres de celda son iguales, llamamos recursivamente con todos los movimientos posibles en ambas direcciones.
Como esto puede llevar a resolver el mismo subproblema varias veces, hemos tomado una nota de mapa en el código a continuación que almacena el resultado calculado con clave como índices de celda inicial y final, por lo que si se vuelve a llamar al subproblema con la misma celda inicial y final, el resultado será devuelto por memo directamente en lugar de volver a calcular de nuevo.
Implementación:
CPP
// C++ program to get number of palindrome
// paths in matrix
#include <bits/stdc++.h>
using namespace std;
#define R 3
#define C 4
// struct to represent state of recursion
// and key of map
struct cells
{
// indices of front cell
int rs, cs;
// indices of end cell
int re, ce;
cells(int rs, int cs, int re, int ce)
: rs(rs)
, cs(cs)
, re(re)
, ce(ce)
{
}
// operator overloading to compare two
// cells which rs needed for map
bool operator<(const cells& other) const
{
return ((rs != other.rs) || (cs != other.cs)
|| (re != other.re) || (ce != other.ce));
}
};
// recursive method to return number
// of palindromic paths in matrix
// (rs, cs) ==> Indices of current cell
// from a starting point (First Row)
// (re, ce) ==> Indices of current cell
// from a ending point (Last Row)
// memo ==> To store results of
// already computed problems
int getPalindromicPathsRecur(char mat[R][C],
int rs, int cs,
int re, int ce,
map<cells, int>& memo)
{
// Base Case 1 : if any index rs out of boundary,
// return 0
if (rs < 0 || rs >= R || cs < 0 || cs >= C)
return 0;
if (re < 0 || re < rs || ce < 0 || ce < cs)
return 0;
// Base case 2 : if values are not equal
// then palindrome property rs not satisfied,
// so return 0
if (mat[rs][cs] != mat[re][ce])
return 0;
// If we reach here, then matrix cells are same.
// Base Case 3 : if indices are adjacent then
// return 1
if (abs((rs - re) + (cs - ce)) <= 1)
return 1;
// if result rs precalculated, return from map
if (memo.find(cells(rs, cs, re, ce))
!= memo.end())
return memo[cells(rs, cs, re, ce)];
int ret = 0; // Initialize result
// calling recursively for all possible movements
ret += getPalindromicPathsRecur(mat, rs + 1,
cs, re - 1,
ce, memo);
ret += getPalindromicPathsRecur(mat, rs + 1,
cs, re,
ce - 1, memo);
ret += getPalindromicPathsRecur(mat, rs,
cs + 1, re - 1,
ce, memo);
ret += getPalindromicPathsRecur(mat, rs,
cs + 1, re,
ce - 1, memo);
// storing the calculated result in map
memo[cells(rs, cs, re, ce)] = ret;
return ret;
}
// method returns number of palindromic paths in matrix
int getPalindromicPaths(char mat[R][C])
{
map<cells, int> memo;
return getPalindromicPathsRecur(mat, 0, 0, R - 1, C - 1,
memo);
}
// Driver code
int main()
{
char mat[R][C] = { 'a', 'a', 'a',
'b', 'b', 'a',
'a', 'a', 'a',
'b', 'b', 'a' };
printf("%d", getPalindromicPaths(mat));
return 0;
}
3
Complejidad de tiempo : O((R x C) 2 )
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.
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