Posted on by Kalkicode
Code Dynamic Programming

# Count number of palindromic path in a matrix

In this article, we will explore a Java program to count the number of palindromic paths in a given matrix. A palindromic path is a path in the matrix that forms a palindrome, meaning it reads the same forwards and backwards. We will provide a problem statement, present a detailed algorithm with explanations, and demonstrate the expected output of the program. Additionally, we will discuss the time complexity of the code.

## Problem Statement

Given a matrix containing characters, we need to count the number of palindromic paths that can be formed using the elements of the matrix. A path can start from any cell and can move in any of the four directions: up, down, left, or right. The path can only move to a neighboring cell if the characters in the current and neighboring cells are the same. Our goal is to find the count of all such palindromic paths in the matrix.

## Algorithm

1. We start by defining a class called "Coordinates" to represent the coordinates of a path in the matrix. It consists of the starting column (`sc`), ending column (`ec`), starting row (`sr`), and ending row (`er`).
2. We create a class named "PalindromicPath" that contains the main logic for counting the palindromic paths.
3. Inside the "PalindromicPath" class, we define a method called `absValue` to calculate the absolute value of a number.
4. We create a method named `countPath` that takes the matrix, a hashmap to store intermediate results (`dp`), and the starting and ending coordinates of a path.
5. We check for boundary conditions: if the coordinates are out of range or if there is an overlap in the path. In such cases, we return 0.
6. If the characters at the start and end coordinates are not the same, we return 0 as well since a palindrome cannot be formed.
7. If the absolute difference between the starting row and ending row plus the starting column and ending column is less than or equal to 1, we have a palindromic path of length 1. In this case, we return 1.
8. Next, we create an instance of the "Coordinates" class with the provided coordinates.
9. We check if the hashmap already contains the current coordinates. If it does, we retrieve the count and return it.
10. If the coordinates are new, we recursively calculate the count of palindromic paths by making four recursive calls:
• Moving down and up: `countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m)`
• Moving left and down: `countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m)`
• Moving right and up: `countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m)`
• Moving right and down: `countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m)`
11. We add up the counts obtained from these recursive calls.
12. Finally, we store the count in the hashmap and return it.
13. In the main function, we create an instance of the "PalindromicPath" class.
14. We define a sample matrix and pass it to the `countPalindromicPath` method.
15. The result is printed on the console.

## Code Solution

``````import java.util.HashMap;
/*
Java Program for
Count number of palindromic path in a matrix
*/
class Coordinates
{
public int sc;
public int ec;
public int sr;
public int er;
public Coordinates(int sc, int ec, int sr, int er)
{
this.sc = sc;
this.ec = ec;
this.sr = sr;
this.er = er;
}
}
public class PalindromicPath
{
public int absValue(int value)
{
if (value < 0)
{
return -value;
}
return value;
}
public int countPath(char[][] matrix, HashMap < Coordinates, Integer > dp, int sc, int ec, int sr, int er, int n, int m)
{
if (sc < 0 || ec < 0 || sr < 0 || er < 0 ||
sc >= m || ec >= m || sr >= n || er >= n)
{
// When index are out of range
return 0;
}
if (sc > ec || sr > er)
{
// Overlapping case
return 0;
}
else if (matrix[er][ec] != matrix[sr][sc])
{
// When palindrome not exist in given indexes
return 0;
}
else if (absValue((sr - er) + (sc - ec)) <= 1)
{
return 1;
}
Coordinates point = new Coordinates(sc, ec, sr, er);
if (dp.containsKey(point))
{
return dp.get(point);
}
// Calculate palindromic path using recursion
int count = countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) +
countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) +
countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) +
countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
dp.put(point, count);
return count;
}
// This function are handling the request of counting palindromic path.
public void countPalindromicPath(char[][] matrix)
{
// Get the length
int n = matrix.length;
int m = matrix[0].length;
// Manage coordinates points
HashMap < Coordinates, Integer > dp =
new HashMap < Coordinates, Integer > ();
int result = countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
System.out.print("\n Result : " + result);
}
public static void main(String[] args)
{
char[][] matrix = {
{
'a' , 'a' , 'a' , 'b'
},
{
'b' , 'b' , 'c' , 'b'
},
{
'b' , 'b' , 'c' , 'a'
},
{
'a' , 'a' , 'b' , 'a'
},
{
'a' , 'b' , 'b' , 'a'
}
};
/*
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  c  c  b  b  a
a  a  b  c  c  b  a  a
a  a  a  c  c  a  a  a
a  a  a  b  b  a  a  a
--------------------------
Result = 7
*/
}
}``````

#### Output

`` Result :  7``
``````// Include header file
#include <iostream>
#include <unordered_map>
#define N 5
#define M 4
using namespace std;
/*
C++ Program for
Count number of palindromic path in a matrix
*/
class Coordinates
{
public: int sc;
int ec;
int sr;
int er;
Coordinates(int sc, int ec, int sr, int er)
{
this->sc = sc;
this->ec = ec;
this->sr = sr;
this->er = er;
}
};
class PalindromicPath
{
public: int absValue(int value)
{
if (value < 0)
{
return -value;
}
return value;
}
int countPath(
char matrix[N][M],
unordered_map <Coordinates*, int > &dp,
int sc,
int ec,
int sr,
int er)
{
if (sc < 0 || ec < 0 || sr < 0 || er < 0 || sc >= M ||
ec >= M || sr >= N || er >= N)
{
// When index are out of range
return 0;
}
if (sc > ec || sr > er)
{
// Overlapping case
return 0;
}
else if (matrix[er][ec] != matrix[sr][sc])
{
// When palindrome not exist in given indexes
return 0;
}
else if (this->absValue((sr - er) + (sc - ec)) <= 1)
{
return 1;
}
Coordinates *point = new Coordinates(sc, ec, sr, er);
if (dp.find(point) != dp.end())
{
return dp[point];
}
// Calculate palindromic path using recursion
int count = this->countPath(matrix, dp, sc, ec, sr + 1, er - 1) +
this->countPath(matrix, dp, sc, ec - 1, sr + 1, er) +
this->countPath(matrix, dp, sc + 1, ec, sr, er - 1) +
this->countPath(matrix, dp, sc + 1, ec - 1, sr, er);
dp[point] = count;
return count;
}
// This function are handling the request of counting palindromic path.
void countPalindromicPath(char matrix[N][M])
{
// Manage coordinates points
unordered_map <Coordinates*, int > dp;
int result = this->countPath(matrix, dp, 0, M - 1, 0, N - 1);
cout << "\n Result : " << result;
}
};
int main()
{
char matrix[N][M] = {
{
'a' , 'a' , 'a' , 'b'
} , {
'b' , 'b' , 'c' , 'b'
} , {
'b' , 'b' , 'c' , 'a'
} , {
'a' , 'a' , 'b' , 'a'
} , {
'a' , 'b' , 'b' , 'a'
}
};
/*
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  c  c  b  b  a
a  a  b  c  c  b  a  a
a  a  a  c  c  a  a  a
a  a  a  b  b  a  a  a
--------------------------
Result = 7
*/
return 0;
}``````

#### Output

`` Result : 7``
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp Program for
Count number of palindromic path in a matrix
*/
public class Coordinates
{
public int sc;
public int ec;
public int sr;
public int er;
public Coordinates(int sc, int ec, int sr, int er)
{
this.sc = sc;
this.ec = ec;
this.sr = sr;
this.er = er;
}
}
public class PalindromicPath
{
public int absValue(int value)
{
if (value < 0)
{
return -value;
}
return value;
}
public int countPath(
char[,] matrix,
Dictionary < Coordinates, int > dp,
int sc, int ec, int sr, int er, int n, int m)
{
if (sc < 0 || ec < 0 || sr < 0 || er < 0 ||
sc >= m || ec >= m || sr >= n || er >= n)
{
// When index are out of range
return 0;
}
if (sc > ec || sr > er)
{
// Overlapping case
return 0;
}
else if (matrix[er,ec] != matrix[sr,sc])
{
// When palindrome not exist in given indexes
return 0;
}
else if (this.absValue((sr - er) + (sc - ec)) <= 1)
{
return 1;
}
Coordinates point = new Coordinates(sc, ec, sr, er);
if (dp.ContainsKey(point))
{
return dp[point];
}
// Calculate palindromic path using recursion
int count = this.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) +
this.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) +
this.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) +
this.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
return count;
}
// This function are handling the request of counting palindromic path.
public void countPalindromicPath(char[,] matrix)
{
// Get the length
int n = matrix.GetLength(0);
int m = matrix.GetLength(1);
// Manage coordinates points
Dictionary < Coordinates, int > dp =
new Dictionary < Coordinates, int > ();
int result = this.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
Console.Write("\n Result : " + result);
}
public static void Main(String[] args)
{
char[,] matrix = {
{
'a' , 'a' , 'a' , 'b'
},
{
'b' , 'b' , 'c' , 'b'
},
{
'b' , 'b' , 'c' , 'a'
},
{
'a' , 'a' , 'b' , 'a'
},
{
'a' , 'b' , 'b' , 'a'
}
};
/*
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  c  c  b  b  a
a  a  b  c  c  b  a  a
a  a  a  c  c  a  a  a
a  a  a  b  b  a  a  a
--------------------------
Result = 7
*/
}
}``````

#### Output

`` Result : 7``
``````package main
import "fmt"
/*
Go Program for
Count number of palindromic path in a matrix
*/
type Coordinates struct {
sc int
ec int
sr int
er int
}
func getCoordinates(sc int, ec int, sr int, er int) * Coordinates {
var me *Coordinates = &Coordinates {}
me.sc = sc
me.ec = ec
me.sr = sr
me.er = er
return me
}
type PalindromicPath struct {}
func getPalindromicPath() * PalindromicPath {
var me *PalindromicPath = &PalindromicPath {}
return me
}
func(this PalindromicPath) absValue(value int) int {
if value < 0 {
return -value
}
return value
}
func(this PalindromicPath) countPath(matrix[][] byte,
dp map[*Coordinates] int, sc int, ec int,
sr int, er int, n int, m int) int {
if sc < 0 || ec < 0 || sr < 0 || er < 0 || sc >= m ||
ec >= m || sr >= n || er >= n {
// When index are out of range
return 0
}
if sc > ec || sr > er {
// Overlapping case
return 0
} else if matrix[er][ec] != matrix[sr][sc] {
// When palindrome not exist in given indexes
return 0
} else if this.absValue((sr - er) + (sc - ec)) <= 1 {
return 1
}
var point * Coordinates = getCoordinates(sc, ec, sr, er)
if _, found := dp[point] ; found {
return dp[point]
}
// Calculate palindromic path using recursion
var count int = this.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) +
this.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) +
this.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) +
this.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m)
dp[point] = count
return count
}
// This function are handling the request of counting palindromic path.
func(this PalindromicPath) countPalindromicPath(matrix[][] byte) {
// Get the length
var n int = len(matrix)
var m int = len(matrix[0])
// Manage coordinates points
var dp = make(map[*Coordinates] int)
var result int = this.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m)
fmt.Print("\n Result : ", result)
}
func main() {
var task * PalindromicPath = getPalindromicPath()
var matrix = [][] byte {
{'a', 'a', 'a', 'b'},
{'b', 'b', 'c', 'b'},
{'b', 'b', 'c', 'a'},
{'a', 'a', 'b', 'a'},
{'a', 'b', 'b', 'a'},
}
/*
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  c  c  b  b  a
a  a  b  c  c  b  a  a
a  a  a  c  c  a  a  a
a  a  a  b  b  a  a  a
--------------------------
Result = 7
*/
}``````

#### Output

`` Result : 7``
``````<?php
/*
Php Program for
Count number of palindromic path in a matrix
*/
class Coordinates
{
public \$sc;
public \$ec;
public \$sr;
public \$er;
public	function __construct(\$sc, \$ec, \$sr, \$er)
{
\$this->sc = \$sc;
\$this->ec = \$ec;
\$this->sr = \$sr;
\$this->er = \$er;
}
public function getValue()
{
return \$this->sc."-".\$this->ec."-".\$this->sr."-".\$this->er;
}
}
class PalindromicPath
{
public	function absValue(\$value)
{
if (\$value < 0)
{
return -\$value;
}
return \$value;
}
public	function countPath(\$matrix, &\$dp, \$sc, \$ec, \$sr, \$er, \$n, \$m)
{
if (\$sc < 0 || \$ec < 0 || \$sr < 0 || \$er < 0 ||
\$sc >= \$m || \$ec >= \$m || \$sr >= \$n || \$er >= \$n)
{
// When index are out of range
return 0;
}
if (\$sc > \$ec || \$sr > \$er)
{
// Overlapping case
return 0;
}
else if (\$matrix[\$er][\$ec] != \$matrix[\$sr][\$sc])
{
// When palindrome not exist in given indexes
return 0;
}
else if (\$this->absValue((\$sr - \$er) + (\$sc - \$ec)) <= 1)
{
return 1;
}
\$point = new Coordinates(\$sc, \$ec, \$sr, \$er);
if (array_key_exists("'".\$point->getValue()."'", \$dp))
{
return \$dp["'".\$point->getValue()."'"];
}
// Calculate palindromic path using recursion
\$count =
\$this->countPath(\$matrix, \$dp, \$sc, \$ec, \$sr + 1, \$er - 1, \$n, \$m) +
\$this->countPath(\$matrix, \$dp, \$sc, \$ec - 1, \$sr + 1, \$er, \$n, \$m) +
\$this->countPath(\$matrix, \$dp, \$sc + 1, \$ec, \$sr, \$er - 1, \$n, \$m) +
\$this->countPath(\$matrix, \$dp, \$sc + 1, \$ec - 1, \$sr, \$er, \$n, \$m);
\$dp["'".\$point->getValue()."'"] = \$count;
return \$count;
}
// This function are handling the request of counting palindromic path.
public	function countPalindromicPath(\$matrix)
{
// Get the length
\$n = count(\$matrix);
\$m = count(\$matrix[0]);
// Manage coordinates points
\$dp = array();
\$result = \$this->countPath(\$matrix, \$dp, 0, \$m - 1, 0, \$n - 1, \$n, \$m);
echo("\n Result : ".\$result);
}
}

function main()
{
\$matrix = array(
array('a', 'a', 'a', 'b'),
array('b', 'b', 'c', 'b'),
array('b', 'b', 'c', 'a'),
array('a', 'a', 'b', 'a'),
array('a', 'b', 'b', 'a')
);
/*
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  c  c  b  b  a
a  a  b  c  c  b  a  a
a  a  a  c  c  a  a  a
a  a  a  b  b  a  a  a
--------------------------
Result = 7
*/
}
main();``````

#### Output

`` Result : 7``
``````/*
Node JS Program for
Count number of palindromic path in a matrix
*/
class Coordinates
{
constructor(sc, ec, sr, er)
{
this.sc = sc;
this.ec = ec;
this.sr = sr;
this.er = er;
}
}
class PalindromicPath
{
absValue(value)
{
if (value < 0)
{
return -value;
}
return value;
}
countPath(matrix, dp, sc, ec, sr, er, n, m)
{
if (sc < 0 || ec < 0 || sr < 0 || er < 0 ||
sc >= m || ec >= m || sr >= n || er >= n)
{
// When index are out of range
return 0;
}
if (sc > ec || sr > er)
{
// Overlapping case
return 0;
}
else if (matrix[er][ec] != matrix[sr][sc])
{
// When palindrome not exist in given indexes
return 0;
}
else if (this.absValue((sr - er) + (sc - ec)) <= 1)
{
return 1;
}
var point = new Coordinates(sc, ec, sr, er);
if (dp.has(point))
{
return dp.get(point);
}
// Calculate palindromic path using recursion
var count = this.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) +
this.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) +
this.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) +
this.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
dp.set(point, count);
return count;
}
// This function are handling the request of counting palindromic path.
countPalindromicPath(matrix)
{
// Get the length
var n = matrix.length;
var m = matrix[0].length;
// Manage coordinates points
var dp = new Map();
var result = this.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
process.stdout.write("\n Result : " + result);
}
}

function main()
{
var matrix = [
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
];
/*
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  c  c  b  b  a
a  a  b  c  c  b  a  a
a  a  a  c  c  a  a  a
a  a  a  b  b  a  a  a
--------------------------
Result = 7
*/
}
main();``````

#### Output

`` Result : 7``
``````#    Python 3 Program for
#    Count number of palindromic path in a matrix
class Coordinates :
def __init__(self, sc, ec, sr, er) :
self.sc = sc
self.ec = ec
self.sr = sr
self.er = er

class PalindromicPath :
def absValue(self, value) :
if (value < 0) :
return -value

return value

def countPath(self, matrix, dp, sc, ec, sr, er, n, m) :
if (sc < 0 or ec < 0 or sr < 0 or er < 0 or sc >= m or
ec >= m or sr >= n or er >= n) :
#  When index are out of range
return 0

if (sc > ec or sr > er) :
#  Overlapping case
return 0
elif (matrix[er][ec] != matrix[sr][sc]) :
#  When palindrome not exist in given indexes
return 0
elif (self.absValue((sr - er) + (sc - ec)) <= 1) :
return 1

point = Coordinates(sc, ec, sr, er)
if ((point in dp.keys())) :
return dp.get(point)

#  Calculate palindromic path using recursion
count = self.countPath(
matrix, dp, sc, ec, sr + 1, er - 1, n, m
) + self.countPath(
matrix, dp, sc, ec - 1, sr + 1, er, n, m
) + self.countPath(
matrix, dp, sc + 1, ec, sr, er - 1, n, m
) + self.countPath(
matrix, dp, sc + 1, ec - 1, sr, er, n, m
)
dp[point] = count
return count

#  This function are handling the request of counting palindromic path.
def countPalindromicPath(self, matrix) :
#  Get the length
n = len(matrix)
m = len(matrix[0])
#  Manage coordinates points
dp = dict()
result = self.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m)
print("\n Result : ", result, end = "")

def main() :
matrix = [
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
]
#    a  b  b  a  a  b  b  a
#    a  b  b  a  a  b  b  a
#    a  b  b  a  a  b  b  a
#    a  b  b  c  c  b  b  a
#    a  a  b  c  c  b  a  a
#    a  a  a  c  c  a  a  a
#    a  a  a  b  b  a  a  a
#    --------------------------
#    Result = 7

if __name__ == "__main__": main()``````

#### Output

`` Result :  7``
``````#    Ruby Program for
#    Count number of palindromic path in a matrix
class Coordinates
# Define the accessor and reader of class Coordinates
attr_accessor :sc, :ec, :sr, :er
def initialize(sc, ec, sr, er)
self.sc = sc
self.ec = ec
self.sr = sr
self.er = er
end

end

class PalindromicPath
def absValue(value)
if (value < 0)
return -value
end

return value
end

def countPath(matrix, dp, sc, ec, sr, er, n, m)
if (sc < 0 || ec < 0 || sr < 0 || er < 0 ||
sc >= m || ec >= m || sr >= n || er >= n)
#  When index are out of range
return 0
end

if (sc > ec || sr > er)
#  Overlapping case
return 0
elsif (matrix[er][ec] != matrix[sr][sc])
#  When palindrome not exist in given indexes
return 0
elsif (self.absValue((sr - er) + (sc - ec)) <= 1)
return 1
end

point = Coordinates.new(sc, ec, sr, er)
if (dp.key?(point))
return dp[point]
end

#  Calculate palindromic path using recursion
count = self.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) +
self.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) +
self.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) +
self.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m)
dp[point] = count
return count
end

#  This function are handling the request of counting palindromic path.
def countPalindromicPath(matrix)
#  Get the length
n = matrix.length
m = matrix[0].length
#  Manage coordinates points
dp = Hash.new()
result = self.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m)
print("\n Result : ", result)
end

end

def main()
matrix = [
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
]
#    a  b  b  a  a  b  b  a
#    a  b  b  a  a  b  b  a
#    a  b  b  a  a  b  b  a
#    a  b  b  c  c  b  b  a
#    a  a  b  c  c  b  a  a
#    a  a  a  c  c  a  a  a
#    a  a  a  b  b  a  a  a
#    --------------------------
#    Result = 7
end

main()``````

#### Output

`` Result : 7``
``````import scala.collection.mutable._;
/*
Scala Program for
Count number of palindromic path in a matrix
*/
class Coordinates(var sc: Int,
var ec: Int,
var sr: Int,
var er: Int);
class PalindromicPath()
{
def absValue(value: Int): Int = {
if (value < 0)
{
return -value;
}
return value;
}
def countPath(matrix: Array[Array[Char]],
dp: HashMap[Coordinates, Int],
sc: Int, ec: Int, sr: Int,
er: Int, n: Int, m: Int): Int = {
if (sc < 0 || ec < 0 || sr < 0 || er < 0 ||
sc >= m || ec >= m || sr >= n || er >= n)
{
// When index are out of range
return 0;
}
if (sc > ec || sr > er)
{
// Overlapping case
return 0;
}
else if (matrix(er)(ec) != matrix(sr)(sc))
{
// When palindrome not exist in given indexes
return 0;
}
else if (absValue((sr - er) + (sc - ec)) <= 1)
{
return 1;
}
var point: Coordinates = new Coordinates(sc, ec, sr, er);
if (dp.contains(point))
{
return dp.get(point).get;
}
// Calculate palindromic path using recursion
var count: Int = countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) +
countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) +
countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) +
countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
return count;
}
// This function are handling the request of counting palindromic path.
def countPalindromicPath(matrix: Array[Array[Char]]): Unit = {
// Get the length
var n: Int = matrix.length;
var m: Int = matrix(0).length;
// Manage coordinates points
var dp: HashMap[Coordinates, Int] = new HashMap[Coordinates, Int]();
var result: Int = countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
print("\n Result : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PalindromicPath = new PalindromicPath();
var matrix: Array[Array[Char]] = Array(
Array('a', 'a', 'a', 'b'),
Array('b', 'b', 'c', 'b'),
Array('b', 'b', 'c', 'a'),
Array('a', 'a', 'b', 'a'),
Array('a', 'b', 'b', 'a')
);
/*
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  c  c  b  b  a
a  a  b  c  c  b  a  a
a  a  a  c  c  a  a  a
a  a  a  b  b  a  a  a
--------------------------
Result = 7
*/
}
}``````

#### Output

`` Result : 7``
``````/*
Kotlin Program for
Count number of palindromic path in a matrix
*/
class Coordinates
{
var sc: Int;
var ec: Int;
var sr: Int;
var er: Int;
constructor(sc: Int, ec: Int, sr: Int, er: Int)
{
this.sc = sc;
this.ec = ec;
this.sr = sr;
this.er = er;
}
}
class PalindromicPath
{
fun absValue(value: Int): Int
{
if (value < 0)
{
return -value;
}
return value;
}
fun countPath(
matrix: Array < Array < Char >> ,
dp: HashMap < Coordinates, Int >  ,
sc : Int, ec: Int, sr: Int,
er: Int, n: Int, m: Int): Int
{
if (sc < 0 || ec < 0 || sr < 0 || er < 0 ||
sc >= m || ec >= m || sr >= n || er >= n)
{
// When index are out of range
return 0;
}
if (sc > ec || sr > er)
{
// Overlapping case
return 0;
}
else if (matrix[er][ec] != matrix[sr][sc])
{
// When palindrome not exist in given indexes
return 0;
}
else if (this.absValue((sr - er) + (sc - ec)) <= 1)
{
return 1;
}
val point: Coordinates = Coordinates(sc, ec, sr, er);
if (dp.containsKey(point))
{
return dp.getValue(point);
}
// Calculate palindromic path using recursion
val count: Int =
this.countPath(matrix, dp, sc, ec, sr + 1, er - 1, n, m) +
this.countPath(matrix, dp, sc, ec - 1, sr + 1, er, n, m) +
this.countPath(matrix, dp, sc + 1, ec, sr, er - 1, n, m) +
this.countPath(matrix, dp, sc + 1, ec - 1, sr, er, n, m);
dp.put(point, count);
return count;
}
// This function are handling the request of counting palindromic path.
fun countPalindromicPath(matrix: Array < Array < Char >> ): Unit
{
// Get the length
val n: Int = matrix.count();
val m: Int = matrix[0].count();
// Manage coordinates points
val dp: HashMap < Coordinates, Int > = HashMap < Coordinates, Int > ();
val result: Int = this.countPath(matrix, dp, 0, m - 1, 0, n - 1, n, m);
print("\n Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
val matrix: Array < Array < Char >> = arrayOf(
arrayOf('a', 'a', 'a', 'b'),
arrayOf('b', 'b', 'c', 'b'),
arrayOf('b', 'b', 'c', 'a'),
arrayOf('a', 'a', 'b', 'a'),
arrayOf('a', 'b', 'b', 'a')
);
/*
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  a  a  b  b  a
a  b  b  c  c  b  b  a
a  a  b  c  c  b  a  a
a  a  a  c  c  a  a  a
a  a  a  b  b  a  a  a
--------------------------
Result = 7
*/
}``````

#### Output

`` Result : 7``

## Expected Output:

The given matrix:

``````a a a b
b b c b
b b c a
a a b a
a b b a
``````

The expected result is 7, indicating that there are seven palindromic paths in the matrix.

## Time Complexity:

The time complexity of this solution is dependent on the size of the matrix. Let's assume the matrix has dimensions `n` x `m`. Since we are using memoization (storing intermediate results in the hashmap), the recursive calls for the same coordinates will have constant time complexity. Therefore, the overall time complexity of the program is O(n * m).

In this article, we discussed a Java program to count the number of palindromic paths in a matrix. We provided a detailed explanation of the algorithm used, along with the problem statement and expected output. Additionally, we analyzed the time complexity of the code. By implementing this program, we can efficiently determine the count of palindromic paths in any given matrix.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post