Posted on by Kalkicode
Code Matrix

# Print all palindromic paths from top left to bottom right

The problem involves finding and printing all palindromic paths from the top left corner of a given matrix to the bottom right corner. A palindromic path is a sequence of elements in the matrix that reads the same from left to right and from top to bottom.

## Example

Consider the following matrix:

a  a  a  b
b  b  c  b
b  b  c  a
a  a  b  a
a  b  b  a

The palindromic paths in this matrix are:

1. a->b->b->a->a->b->b->a
2. a->b->b->a->a->b->b->a
3. a->b->b->a->a->b->b->a
4. a->b->b->c->c->b->b->a
5. a->a->b->c->c->b->a->a
6. a->a->a->c->c->a->a->a
7. a->a->a->b->b->a->a->a

## Idea to Solve the Problem

To find all palindromic paths, we need to explore all possible paths from the top left corner to the bottom right corner of the matrix. While traversing the paths, we need to keep track of the elements visited so far and check if the current path is palindromic. If it is, we print the path.

## Algorithm

1. Define a function palindrome that checks if a given array result[] from index start to index last is palindromic.
2. Define a function palindrome_path that takes the matrix matrix[R][C], the array result[], the current row and col, the counter of elements visited, and the k value (size of the path) as parameters.
• If the current row or column is out of bounds, return.
• Add the current element of the matrix to the result[] array.
• Recursively call palindrome_path for the next row or column.
• If the current path contains k elements and is palindromic, print the path elements.
3. In the main function:
• Define the matrix matrix[R][C].
• Calculate the maximum size of a palindromic path (sum of rows and columns - 1).
• Define an array result[] to store the path.
• Call the palindrome_path function with initial parameters.

## Pseudocode

palindrome(start, last, result):
status = 1
while start < last and status == 1:
if result[start] is not equal to result[last]:
set status to 0
increment start and decrement last
return status

palindrome_path(matrix, result, row, col, counter, k):
if row >= R or col >= C:
return
add matrix[row][col] to result at index counter
call palindrome_path with row+1, col, counter+1, k
call palindrome_path with row, col+1, counter+1, k
if counter+1 is equal to k and palindrome(result, 0, k-1):
loop through i from 0 to k-1:
print result[i]
print a newline

main:
matrix = ...  // Define the matrix
calculate maximum path size and store in size
define result array of size size
call palindrome_path with matrix, result, 0, 0, 0, size

## Code Solution

//C Program
//Print all palindromic paths from top left to bottom right
#include <stdio.h>

//size of matrix
#define R 5
#define C 4
//Function which is check palindromic path in given resultant array
int palindrome(char result[], int start, int last)
{
int status = 1;
while (start < last && status == 1)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = 0;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
void palindrome_path(char matrix[R][C],
char result[],
int row, int col,
int counter, int k)
{
if (row >= R || col >= C)
{
return;
}
//Get a new element of path
result[counter] = matrix[row][col];
palindrome_path(matrix, result, row + 1, col, counter + 1, k);
palindrome_path(matrix, result, row, col + 1, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && palindrome(result, 0, k - 1))
{
// When resultant path contains palindrome
// Display path elements
for (int i = 0; i < k; ++i)
{
printf("%3c", result[i]);
}
printf("\n");
}
}
int main()
{
char matrix[R][C] =
{
{'a', 'a', 'a', 'b'},
{'b', 'b', 'c', 'b'},
{'b', 'b', 'c', 'a'},
{'a', 'a', 'b', 'a'},
{'a', 'b', 'b', 'a'}
};
//Possible size of palindromic path
int size = R + C - 1;
//Auxiliary space which is used in stored the path of palindrome
char result[size];
palindrome_path(matrix, result, 0, 0, 0, size);
return 0;
}

#### Output

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
/*
Java Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
public boolean palindrome(char[] result, int start, int last)
{
boolean status = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
public void palindrome_path(char[][] matrix, char[] result, int r, int c, int row_size, int col_size, int counter, int k)
{

if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r][c];
palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for (int i = 0; i < k; ++i)
{
System.out.print("  " + result[i]);
}
System.out.print("\n");
}
}
public static void main(String[] args)
{
MyMatrix obj = new MyMatrix();
char[][] matrix = {
{'a', 'a', 'a', 'b'},
{'b', 'b', 'c', 'b'},
{'b', 'b', 'c', 'a'},
{'a', 'a', 'b', 'a'},
{'a', 'b', 'b', 'a'}
};
int row_size = matrix.length;
int col_size = matrix[0].length;
//Possible size of palindromic path
int size = row_size + col_size - 1;
//Auxiliary space which is used in stored the path of palindrome
char[] result = new char[size];
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size);
}
}

#### Output

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
/*
C++ Program
Print all palindromic paths from top left to bottom right
*/
#include<iostream>
//size of matrix
#define R 5
#define C 4
using namespace std;
class MyMatrix
{
public:
//Function which is check palindromic path in given resultant array
bool palindrome(char *result, int start, int last)
{
bool status = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
void palindrome_path(char matrix[R][C], char *result, int r, int c, int row_size, int col_size, int counter, int k)
{
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r][c];
this->palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
this->palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && this->palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for (int i = 0; i < k; ++i)
{
cout << "  " << result[i];
}
cout << "\n";
}
}
};
int main()
{
MyMatrix obj =  MyMatrix();
char matrix[R][C] = {
{
'a',
'a',
'a',
'b'
},
{
'b',
'b',
'c',
'b'
},
{
'b',
'b',
'c',
'a'
},
{
'a',
'a',
'b',
'a'
},
{
'a',
'b',
'b',
'a'
}
};

//Possible size of palindromic path
int size = R + C - 1;
char *result = new char[size];
obj.palindrome_path(matrix, result, 0, 0, R, C, 0, size);
return 0;
}

#### Output

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
/*
C# Program
Print all palindromic paths from top left to bottom right
*/
using System;
class MyMatrix
{
//Function which is check palindromic path in given resultant array
public Boolean palindrome(char[] result, int start, int last)
{
Boolean status = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
public void palindrome_path(char[,] matrix, char[] result, int r, int c, int row_size, int col_size, int counter, int k)
{
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r,c];
palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for (int i = 0; i < k; i++)
{
Console.Write("  " + result[i]);
}
Console.Write("\n");
}
}
public static void Main(String[] args)
{
MyMatrix obj = new MyMatrix();
char[,] matrix = {
{
'a',
'a',
'a',
'b'
},
{
'b',
'b',
'c',
'b'
},
{
'b',
'b',
'c',
'a'
},
{
'a',
'a',
'b',
'a'
},
{
'a',
'b',
'b',
'a'
}
};
int row_size = matrix.GetLength(0);
int col_size = matrix.GetLength(1);
//Possible size of palindromic path
int size = row_size + col_size - 1;
char[] result = new char[size];
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size);
}
}

#### Output

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
<?php
/*
Php Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
public 	function palindrome( & \$result, \$start, \$last)
{
\$status = true;
while (\$start < \$last && \$status == true)
{
if (\$result[\$start] != \$result[\$last])
{
//When two boundary elements are not same
\$status = false;
}
\$start++;
\$last--;
}
return \$status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
public 	function palindrome_path( & \$matrix, & \$result, \$r, \$c, \$row_size, \$col_size, \$counter, \$k)
{
if (\$r >= \$row_size || \$c >= \$col_size)
{
return;
}
//Get a new element of path
\$result[\$counter] = \$matrix[\$r][\$c];
\$this->palindrome_path(\$matrix, \$result, \$r + 1, \$c, \$row_size, \$col_size, \$counter + 1, \$k);
\$this->palindrome_path(\$matrix, \$result, \$r, \$c + 1, \$row_size, \$col_size, \$counter + 1, \$k);
//Check whether path contains k elements and
//path contains palindrome or not
if (\$counter + 1 == \$k && \$this->palindrome(\$result, 0, \$k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for (\$i = 0; \$i < \$k; ++\$i)
{
echo("  ". \$result[\$i]);
}
echo("\n");
}
}
}

function main()
{
\$obj = new MyMatrix();
\$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')
);
\$row_size = count(\$matrix);
\$col_size = count(\$matrix[0]);
//Possible size of palindromic path
\$size = \$row_size + \$col_size - 1;
//Auxiliary space which is used in stored the path of palindrome
\$result = array_fill(0, \$size, ' ');
\$obj->palindrome_path(\$matrix, \$result, 0, 0, \$row_size, \$col_size, 0, \$size);
}
main();

#### Output

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
/*
Node Js Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
palindrome(result, start, last)
{
var status = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start++;
last--;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
palindrome_path(matrix, result, r, c, row_size, col_size, counter, k)
{
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r][c];
this.palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
this.palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && this.palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
for (var i = 0; i < k; ++i)
{
process.stdout.write("  " + result[i]);
}
process.stdout.write("\n");
}
}
}

function main(args)
{
var obj = new MyMatrix();
var matrix = [
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
];
var row_size = matrix.length;
var col_size = matrix[0].length;
//Possible size of palindromic path
var size = row_size + col_size - 1;
//Auxiliary space which is used in stored the path of palindrome
var result = Array(size).fill(' ');
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size);
}
main();

#### Output

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
#   Ruby Program
#   Print all palindromic paths from top left to bottom right

class MyMatrix

# Function which is check palindromic path in given resultant array
def palindrome(result, start, last)

status = true
while (start < last && status == true)

if (result[start] != result[last])

# When two boundary elements are not same
status = false
end
start += 1
last -= 1
end
return status
end
# Get all paths from top left to bottom right
# And display of all exist palindromic paths
def palindrome_path(matrix, result, r, c, row_size, col_size, counter, k)

if (r >= row_size || c >= col_size)

return
end
# Get a new element of path
result[counter] = matrix[r][c]
self.palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k)
self.palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k)
# Check whether path contains k elements and
# path contains palindrome or not
if (counter + 1 == k && self.palindrome(result, 0, k - 1) == true)

#  When resultant path contains palindrome
#  Display path elements
i = 0
while (i < k)

print("  ", result[i])
i += 1
end
print("\n")
end
end
end
def main()

obj = MyMatrix.new()
matrix = [
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
]
row_size = matrix.length
col_size = matrix[0].length
# Possible size of palindromic path
size = row_size + col_size - 1
result = Array.new(size, ' ')
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size)
end
main()

#### Output

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
#   Python 3 Program
#   Print all palindromic paths from top left to bottom right

class MyMatrix :
# Function which is check palindromic path in given resultant array
def palindrome(self, result, start, last) :
status = True
while (start < last and status == True) :
if (result[start] != result[last]) :
# When two boundary elements are not same
status = False

start += 1
last -= 1

return status

# Get all paths from top left to bottom right
# And display of all exist palindromic paths
def palindrome_path(self, matrix, result, r, c, row_size, col_size, counter, k) :
if (r >= row_size or c >= col_size) :
return

# Get a new element of path
result[counter] = matrix[r][c]
self.palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k)
self.palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k)
# Check whether path contains k elements and
# path contains palindrome or not
if (counter + 1 == k and self.palindrome(result, 0, k - 1) == True) :
#  When resultant path contains palindrome
#  Display path elements
i = 0
while (i < k) :
print(" ", result[i], end = "")
i += 1

print("\n", end = "")

def main() :
obj = MyMatrix()
matrix = [
['a', 'a', 'a', 'b'],
['b', 'b', 'c', 'b'],
['b', 'b', 'c', 'a'],
['a', 'a', 'b', 'a'],
['a', 'b', 'b', 'a']
]
row_size = len(matrix)
col_size = len(matrix[0])
# Possible size of palindromic path
size = row_size + col_size - 1
result = [' '] * size
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size)

if __name__ == "__main__": main()

#### Output

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
/*
Scala Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
def palindrome(result: Array[Character], s: Int, e: Int): Boolean = {
var start = s;
var last  = e;
var status: Boolean = true;
while (start < last && status == true)
{
if (result(start) != result(last))
{
//When two boundary elements are not same
status = false;
}
start += 1;
last -= 1;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
def palindrome_path(matrix: Array[Array[Character]], result: Array[Character], r: Int, c: Int, row_size: Int, col_size: Int, counter: Int, k: Int): Unit = {
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result(counter) = matrix(r)(c);
palindrome_path(matrix, result, r + 1, c, row_size, col_size, counter + 1, k);
palindrome_path(matrix, result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
var i: Int = 0;
while (i < k)
{
print("  " + result(i));
i += 1;
}
print("\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyMatrix = new MyMatrix();
var matrix: Array[Array[Character]] = 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')
);
var row_size: Int = matrix.length;
var col_size: Int = matrix(0).length;
//Possible size of palindromic path
var size: Int = row_size + col_size - 1;
var result: Array[Character] = Array.fill[Character](size)(' ');
obj.palindrome_path(matrix, result, 0, 0, row_size, col_size, 0, size);
}
}

#### Output

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
/*
Swift Program
Print all palindromic paths from top left to bottom right
*/
class MyMatrix
{
//Function which is check palindromic path in given resultant array
func palindrome(_ result: [Character], _ s:  Int, _ e:  Int) -> Bool
{
var start = s;
var last = e;
var status: Bool = true;
while (start < last && status == true)
{
if (result[start] != result[last])
{
//When two boundary elements are not same
status = false;
}
start += 1;
last -= 1;
}
return status;
}
//Get all paths from top left to bottom right
//And display of all exist palindromic paths
func palindrome_path(_ matrix: [[Character]], _ result: inout[Character], _ r: Int, _ c: Int, _ row_size: Int, _ col_size: Int, _ counter: Int, _ k: Int)
{
if (r >= row_size || c >= col_size)
{
return;
}
//Get a new element of path
result[counter] = matrix[r][c];
self.palindrome_path(matrix, &result, r + 1, c, row_size, col_size, counter + 1, k);
self.palindrome_path(matrix, &result, r, c + 1, row_size, col_size, counter + 1, k);
//Check whether path contains k elements and
//path contains palindrome or not
if (counter + 1 == k && self.palindrome(result, 0, k - 1) == true)
{
// When resultant path contains palindrome
// Display path elements
var i: Int = 0;
while (i < k)
{
print("  ", result[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
}
}
func main()
{
let obj: MyMatrix = MyMatrix();
let matrix: [
[Character]
] = [
["a", "a", "a", "b"],
["b", "b", "c", "b"],
["b", "b", "c", "a"],
["a", "a", "b", "a"],
["a", "b", "b", "a"]
];
let row_size: Int = matrix.count;
let col_size: Int = matrix[0].count;
//Possible size of palindromic path
let size: Int = row_size + col_size - 1;
var result: [Character] = Array(repeating: " ", count: size);
obj.palindrome_path(matrix, &result, 0, 0, row_size, col_size, 0, size);
}
main();

#### Output

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

## Output Explanation

The mentioned C code implements the above algorithm to find and print all palindromic paths in the given matrix. It explores all possible paths and checks if each path is palindromic. If a palindromic path is found, it prints the path elements.

## Time Complexity

The time complexity of the algorithm depends on the number of paths explored and the time complexity of the palindrome function. In the worst case, the algorithm explores all paths from the top left to the bottom right corner, which is exponential. Additionally, the palindrome function takes O(k) time to check if a path is palindromic, where k is the size of the path. Therefore, the overall time complexity can be considered as O(2^(R+C)) * O(k), where R is the number of rows, C is the number of columns, and k is the maximum path size.

## 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