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

/div>

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

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter