Palindrome Paths
Time limit2sMemory limit128 MB
Count length-L walks on an N x N grid with 8-directional moves whose visited digit sequence forms a palindrome.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Matrix, Graph
- Solved
- No attempts yet
Problem
An N x N array contains digits from 0 to 9. A path starts from any cell and then moves to one of the 8 neighboring cells, including diagonal neighbors, on each step. A complete path visits exactly L cells, including the starting cell.
If the digits written on the visited cells, read in visiting order, form a palindrome, the path is called a palindrome path.
The same cell may be visited more than once. However, a move may not stay in the same cell, so each step must move to a different adjacent cell. Moving back to a previously visited cell is allowed.
Given the array, count the number of palindrome paths.
A palindrome is a sequence that reads the same from the front and from the back. The sequences {1}, {1 1}, and {1 3 1} are palindromes.
Input
The first line contains N and L. (1 <= N <= 20, 1 <= L <= 20)
Each of the next N lines contains one row of the array: N integers between 0 and 9, separated by spaces.
Output
Print the number of palindrome paths. This value is at most 2^31 - 1.