| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB | 24 | 7 | 7 | 29.167% |
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)\}^Q_{i=1}$ 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.
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.
a, b, ... , z$\}$ is a lowercase letter.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.
ICPC > Regionals > Asia Pacific > Taiwan > Taiwan Online Programming Contest > TOPC 2022 A번