410237: GYM103990 A AibohphobiA

You are given a rectangular grid of $$$M$$$ rows and $$$N$$$ columns. The rows and columns are indexed from $$$0$$$ to $$$M-1$$$ and from $$$0$$$ to $$$N-1$$$ respectively. In each grid cell $$$(i, j)$$$, there is a lowercase letter character $$$A[i, j]$$$. This grid represents a maze, and the goal to solve the maze is to find a walk going from $$$(0, 0)$$$ to $$$(M-1, N-1)$$$. The walk consists of several steps. In each step you can choose one of the four directions (going from a grid cell to a neighboring cell that shares an edge.) Notice that it is okay to revisit a cell multiple times during the walk, including the starting cell $$$(0, 0)$$$ and the ending cell $$$(M-1, N-1)$$$. If you record all characters along the walk, you'll get a string that represents this walk.

Truckski is not a fan of palindromes, so he would like to find a walk that does not contain any palindromic substrings of length at least two, which he called a good walk. A string $$$s_1s_2\cdots s_k$$$ is called a palindrome, if it reads the same after reversing the string, i.e., $$$s_1s_2\cdots s_k=s_ks_{k-1}\cdots s_1$$$. A substring of a string can be obtained by removing a (possibly empty) prefix and a (possibly empty) suffix.

Now, there are $$$Q$$$ interesting locations $$$\{(r_i, c_i)\}_{i=1}^Q$$$ that Truckski wishes to visit. For each location $$$(r_i, c_i)$$$, can you help Truckski to find the length of the longest good walk that visits the location grid cell $$$(r_i, c_i)$$$ at least once? If there are arbitrarily long good walks please output -1. If there does not exist any good walk, please output -2.

The first line contains an integer $$$T$$$, indicating the number of test cases. For each test case, there are two integers $$$M$$$ and $$$N$$$ in the first line. In each of the following $$$M$$$ lines there is a string of length $$$N$$$, the $$$c$$$-th character in the $$$r$$$-th line is the character $$$A[r, c]$$$. The next line contains an integer $$$Q$$$. In each of the following $$$Q$$$ lines there are two integers $$$r_i$$$ and $$$c_i$$$ indicating the location of interest.

• $$$T \le 20$$$
• $$$2 \le M \le 100$$$
• $$$2 \le N \le 100$$$
• $$$1 \le Q \le 100$$$
• For all $$$i$$$ such that $$$1\le i \le Q$$$, $$$0\le r_i < M$$$ and $$$0\le c_i < N$$$.
• For each grid cell $$$(r, c)$$$, $$$A[r, c]\in \{\texttt{a},\texttt{b},\ldots, \texttt{z}\}$$$ is a lowercase letter.

For each interesting location, output the length of the longest good walk that visits this location at least once, or -1 if the good walk can be arbitrarily long, or -2 if there does not exist such a good walk.

3
3 5
abbba
bccab
cabcc
2
0 1
1 0
3 4
aaba
bbaa
abab
1
1 1
4 4
abca
cxxb
bxxc
acba
1
0 1

9
9
-2
-1

This problem is not the easiest problem in this contest.