Tutorialspoint.dev

Print all palindromic paths from top left to bottom right in a matrix

Given a matrix containing lower alphabetical characters only, we need to print all palindromic paths in given matrix. A path is defined as a sequence of cells starting from top-left cell and ending at bottom-right cell. We are allowed to move to right and down only from current cell. We cannot go down diagonally.
Example:

Input : mat[][] = {"aaab”, 
                   "baaa”
                   “abba”}
Output :aaaaaa, aaaaaa, abaaba

Explanation :
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)

Order of elements in the output array doesn’t matter.



The idea is simple. We start from top left (0, 0) and explore all paths to bottom right. If a path turns to be palindrome, we print it.

C++

// C++ program to print all palindromic paths
// from top left to bottom right in a grid.
#include<bits/stdc++.h>
using namespace std;
#define N 4
bool isPalin(string str)
{
    int len = str.length() / 2;
    for (int i = 0; i < len; i++) 
    {
        if (str[i] != str[str.length() - i - 1])
            return false;
    }
    return true;
}
  
// i and j are row and column indexes of current cell 
// (initially these are 0 and 0).
void palindromicPath(string str, char a[][N],
                            int i, int j, int m, int n)
{
          
    // If we have not reached bottom right corner, keep
    // exlporing
    if (j < m - 1 || i < n - 1) 
    {
        if (i < n - 1)
            palindromicPath(str + a[i][j], a, i + 1, j, m, n);
        if (j < m - 1)
            palindromicPath(str + a[i][j], a, i, j + 1, m, n);
    
  
    // If we reach bottom right corner, we check if
    // if the path used is palindrome or not.
    else {
        str = str + a[n - 1][m - 1];
        if (isPalin(str))
            cout<<(str)<<endl;
    }
}
  
// Driver code 
int main()
{
    char arr[][N] = { { 'a', 'a', 'a', 'b' },
                    { 'b', 'a', 'a', 'a' },
                    { 'a', 'b', 'b', 'a' } };
    string str = "";
    palindromicPath(str, arr, 0, 0, 4, 3);
    return 0;
}
  
// This code is contributed by andrew1234

Java

// Java program to print all palindromic paths
// from top left to bottom right in a grid.
public class PalinPath {
    public static boolean isPalin(String str)
    {
        int len = str.length() / 2;
        for (int i = 0; i < len; i++) {
            if (str.charAt(i) != str.charAt(str.length() - i - 1))
                return false;
        }
        return true;
    }
  
    // i and j are row and column indexes of current cell 
    // (initially these are 0 and 0).
    public static void palindromicPath(String str, char a[][],
                                 int i, int j, int m, int n)
    {
            
        // If we have not reached bottom right corner, keep
        // exlporing
        if (j < m - 1 || i < n - 1) {
          if (i < n - 1)
             palindromicPath(str + a[i][j], a, i + 1, j, m, n);
         if (j < m - 1)
             palindromicPath(str + a[i][j], a, i, j + 1, m, n);
        
  
        // If we reach bottom right corner, we check if
        // if the path used is palindrome or not.
        else {
            str = str + a[n - 1][m - 1];
            if (isPalin(str))
                System.out.println(str);
        }
    }
  
    // Driver code 
    public static void main(String args[])
    {
        char arr[][] = { { 'a', 'a', 'a', 'b' },
                         { 'b', 'a', 'a', 'a' },
                         { 'a', 'b', 'b', 'a' } };
        String str = "";
        palindromicPath(str, arr, 0, 0, 4, 3);
    }
}

Python 3

# Python 3 program to print all 
# palindromic paths from top left
# to bottom right in a grid.
  
def isPalin(str):
  
    l = len(str) // 2
    for i in range( l) :
        if (str[i] != str[len(str) - i - 1]):
            return False
          
    return True
  
# i and j are row and column 
# indexes of current cell 
# (initially these are 0 and 0).
def palindromicPath(str, a, i, j, m, n):
          
    # If we have not reached bottom 
    # right corner, keep exlporing
    if (j < m - 1 or i < n - 1) :
        if (i < n - 1):
            palindromicPath(str + a[i][j], a, 
                            i + 1, j, m, n)
        if (j < m - 1):
            palindromicPath(str + a[i][j], a, 
                            i, j + 1, m, n) 
  
    # If we reach bottom right corner, 
    # we check if the path used is
    # palindrome or not.
    else :
        str = str + a[n - 1][m - 1]
        if isPalin(str):
            print(str)
  
# Driver code 
if __name__ == "__main__":
      
    arr = [[ 'a', 'a', 'a', 'b' ],
           ['b', 'a', 'a', 'a' ],
           [ 'a', 'b', 'b', 'a' ]]
    str = ""
    palindromicPath(str, arr, 0, 0, 4, 3)
  
# This code is contributed 
# by ChitraNayal

C#

// C# program to print all palindromic paths 
// from top left to bottom right in a grid. 
using System;
  
class GFG
{
public static bool isPalin(string str)
{
    int len = str.Length / 2;
    for (int i = 0; i < len; i++)
    {
        if (str[i] != str[str.Length - i - 1])
        {
            return false;
        }
    }
    return true;
}
  
// i and j are row and column indexes of 
// current cell (initially these are 0 and 0). 
public static void palindromicPath(string str, char[][] a, 
                                   int i, int j, int m, int n)
{
  
    // If we have not reached bottom 
    // right corner, keep exlporing 
    if (j < m - 1 || i < n - 1)
    {
    if (i < n - 1)
    {
        palindromicPath(str + a[i][j],
                        a, i + 1, j, m, n);
    }
    if (j < m - 1)
    {
        palindromicPath(str + a[i][j],
                        a, i, j + 1, m, n);
    }
    }
  
    // If we reach bottom right corner,
    // we check if the path used is
    // palindrome or not. 
    else
    {
        str = str + a[n - 1][m - 1];
        if (isPalin(str))
        {
            Console.WriteLine(str);
        }
    }
}
  
// Driver code 
public static void Main(string[] args)
{
    char[][] arr = new char[][]
    {
        new char[] {'a', 'a', 'a', 'b'},
        new char[] {'b', 'a', 'a', 'a'},
        new char[] {'a', 'b', 'b', 'a'}
    };
    string str = "";
    palindromicPath(str, arr, 0, 0, 4, 3);
}
}
  
// This code is contributed by Shrikant13


Output :

abaaba
aaaaaa
aaaaaa

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter