CF1740D Knowledge Cards
题目描述
### 题目大意
对于一个 $n \times m$ 的棋盘，左上角为 $(1,\;1)$，右下角为 $(n,\;m)$。$(1,\;1)$ 和 $(n,\;m)$ 上分别有一个栈。最开始的时候$(1,\;1)$ 格子上的栈里有 $k$ 张牌，**从栈顶到栈底**的第 $i$ 张牌上有一个数 $a_i$，保证 $a$ 数组是一个 $k$ 的全排列。你需要对这些牌做若干次操作将所有牌移到 $(n,\;m)$ 格子的栈中，使得最后 $(n,\;m)$ 格子的栈中从上到下牌上的序号依次为 $1 \sim k$，每次给你棋盘长宽 $n \times m$ 和初始的 $a$ 数组，请问是否有解。
我们定义一次操作的规则如下：
1. 一次只能操作一张牌；
2. 一张牌只能向相邻的**四联通**格子（有共边）里移动；
3. **除了** $(1,\;1)$ 和 $(n,\;m)$ 以外的格子内不能拥有超过一张牌；
4. 如果你当前**操作**的格子是 $(1,\;1)$，那么你只能从他的**栈顶**取走一张牌，且你**不能**将一张牌移到他上面；
5. 如果你当前操作的**目标**格子是 $(n,\;m)$，那么你只能将一张牌移动到他的**栈顶**，且你不能从他上面移走任何一张牌。
输入格式
第一行一个整数 $T\;(1 \leqslant T \leqslant 2\cdot10^4)$ 表示测试样例数。
对于每一组测试样例，第一行三个整数 $n,\;m,\;k\;(3 \leqslant n,m \leqslant 10^6,\;n \cdot m \leqslant 10^6,\;1 \leqslant k \leqslant 10^5)$，分别表示棋盘大小和初始牌数。
接下来的一行 $k$ 个整数，表示 $a_1 \sim a_k$ ，意义见题目大意。
数据保证 $\sum n \cdot m \leqslant 10^6,\sum k \leqslant 10^5$。
输出格式
对于每一组输出样例输出包含一行，如果有解则输出 "YA"（不包含引号），否则输出 "TIDAK"（不包含引号）。（数据不区分大小写）
$Translated \; by \; Zigh$
说明/提示
In the first test case, the following is one way the puzzle can be done:
- Move the card with $ 3 $ written on it from cell $ (1, 1) $ to cell $ (1, 2) $ , then cell $ (1, 3) $ .
- Move the card with $ 6 $ written on it from cell $ (1, 1) $ to cell $ (2, 1) $ , then cell $ (3, 1) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ .
- Move the card with $ 4 $ written on it from cell $ (1, 1) $ to cell $ (1, 2) $ .
- Move the card with $ 1 $ written on it from cell $ (1, 1) $ to cell $ (2, 1) $ , then cell $ (2, 2) $ , then cell $ (2, 3) $ .
- Move the card with $ 2 $ written on it from cell $ (1, 1) $ to cell $ (2, 1) $ , then cell $ (2, 2) $ .
- Move the card with $ 5 $ written on it from cell $ (1, 1) $ to cell $ (2, 1) $ , then cell $ (3, 1) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ .
- Move the card with $ 2 $ written on it from cell $ (2, 2) $ to cell $ (2, 1) $ .
- Move the card with $ 4 $ written on it from cell $ (1, 2) $ to cell $ (2, 2) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ .
- Move the card with $ 3 $ written on it from cell $ (1, 3) $ to cell $ (1, 2) $ , then cell $ (2, 2) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ .
- Move the card with $ 2 $ written on it from cell $ (2, 1) $ to cell $ (3, 1) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ .
- Move the card with $ 1 $ written on it from cell $ (2, 3) $ to cell $ (3, 3) $ .
An animated illustration regarding the process mentioned above is as follows:
