This problem was asked in a contest conducted today called 'GitHub Code Geek Fest' (I think it is only for partner colleges in India).
Problem Statement:
Given a grid with N rows (numbered from 1 to N) and M columns (numbered from 1 to M) consisting of upper case English characters.
You are initially in the cell (1,1) and you want to go to cell (N,M) such that the path you follow is Palindromic.
During each move, you either move to the next cell in the current row, or in the current column, i.e, if the current cell is (x,y), then after the move it can be either (x+1,y) or (x,y+1). (Basically, you can either move to the right or down).
A path is called Palindromic if the letter in the first cell is equal to the letter in the last cell, the letter in the second cell is equal to the letter in the second-to last cell, and so on.
Also, you can increment or decrement a letter at some position (i,j) with the cost of 1 unit. Incrementing a letter changes it to the next letter in the alphabet (e.g., 'A' to 'B', 'L' to 'M', and 'Y' to 'Z'). Decrementing a letter changes it to the previous letter in the alphabet (e.g., 'B' to 'A', 'M' to 'L', and 'Z' to 'Y').
The letter 'A' cannot be decremented and the letter 'Z' cannot be incremented. Multiple operations may be applied to the same index.
Find the minimum cost incurred for a path from (1,1) to (N,M) such that the path is Palindromic.
Constraints:
- 1 ≤ N,M ≤ 100
- The values in the grid only consist of uppercase English letters
Test Cases:
(The problem setters didn't provide any test cases, I came up with these)
Input:
4 4
A X Y Z
C D X Y
P Z E S
Q R B A
Output: 2 (If we follow the path A->C->D->Z->E->B->A, we can change C to B (cost : 1) and D to E (cost : 1) to make the path palindrome)
Input:
4 3
H E Y
H H L
C H H
Z Y H
Output: 0 (We follow the path H->H->H->H->H->H, It is already a palindrome, we don't have to perform any operation)
I initially thought of a DP approach, but couldn't figure out the transitions properly. Any help would be appreciated.
