Skip to main content

Count number of palindromic path in a matrix

Here given code implementation process.

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))
		{
			// When point already exists
			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)
	{
		PalindromicPath task = new PalindromicPath();
		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
		*/
		task.countPalindromicPath(matrix);
	}
}

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())
        {
            // When point already exists
            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()
{
    PalindromicPath *task = new PalindromicPath();
    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
    */
    task->countPalindromicPath(matrix);
    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))
		{
			// When point already exists
			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);
		dp.Add(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.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)
	{
		PalindromicPath task = new PalindromicPath();
		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
		*/
		task.countPalindromicPath(matrix);
	}
}

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 {
		// When point already exists
		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
	*/
	task.countPalindromicPath(matrix)
}

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))
		{
			// When point already exists
			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()
{
	$task = new PalindromicPath();
	$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
	*/
	$task->countPalindromicPath($matrix);
}
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))
		{
			// When point already exists
			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 task = new PalindromicPath();
	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
	*/
	task.countPalindromicPath(matrix);
}
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())) :
			#  When point already exists
			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() :
	task = PalindromicPath()
	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
	task.countPalindromicPath(matrix)

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_reader :sc, :ec, :sr, :er
	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)) 
			#  When point already exists
			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() 
	task = PalindromicPath.new()
	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
	task.countPalindromicPath(matrix)
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))
		{
			// When point already exists
			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);
		dp.addOne(point, count);
		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
		*/
		task.countPalindromicPath(matrix);
	}
}

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))
		{
			// When point already exists
			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 task: PalindromicPath = PalindromicPath();
	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
	*/
	task.countPalindromicPath(matrix);
}

Output

 Result : 7




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.

New Comment