*Difficulty: Medium

Given a matrix containing lower alphabetical characters only, we need to count number of 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.

The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines.
First line of each test case consist of two space separated integers R and C, denoting the number of element in a row and column respectively.
Second line of each test case consists of R*C space separated chars denoting the elements in the matrix in row major order.

It should be single line output, Print the respective output in the respective line.



3 4
a a a b b a a a a b b a


Approach: Recursion

Source: Algorithms



As we can only move right or down, we need to keep track of when we reach the bottom or the right side. As soon as we reach those, we either go right straight to the destination or go down straight to the destination (As described in the photo above). So the recursion will have two recursion calls and two base cases. One recursion call to move right (increase col), and one to move down (increase row), one base case when we reach bottom and one when we reach right side. In my opinion, it’s easier to implement problem solving in Python, so let’s get started.
But before we jump in to the code, here’s the picture shows how the recursion works under the hood:


Implementation: Python 2.7

def all_paths(matrix, row, col, path, paths):
        generate all possible paths from top-left to botrom right
        by only moving right and down from current cell.
    # touch the bottom, go all the way right to destination
    if row == len(matrix)-1: 
        for i in range(col, len(matrix[0])):
            path += matrix[row][i]
    # touch the right side, go all the way down to destination
    if col == len(matrix[0])-1:
        for i in range(row, len(matrix)):
            path += matrix[i][col]
    path += matrix[row][col]
    # go right
    all_paths(matrix, row+1, col, path, paths)
    # and go down
    all_paths(matrix, row, col+1, path, paths)    

def is_palindrom(string):
    bound = len(string) // 2
    for i in range(bound):
        if string[i] != string[len(string)-1-i]:
            return False
    return True

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n, m = map(int, raw_input().strip().split())
        line = raw_input().strip().split()
        matrix = []
        for i in range(0, len(line), m):
        all_possible_paths, count_palindroms = [], 0
        all_paths(matrix, 0, 0, "", all_possible_paths)
        for path in all_possible_paths:
            if is_palindrom(path):
                count_palindroms += 1
        print count_palindroms