A1435 | 纸牌游戏
来源官方 / 2023
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
著名学者 $AC$ 狗君发明了一个纸牌游戏，在游戏中，有一个 $n \times m$ 的棋盘，$(r,c)$ 表示棋盘中第 $r$ 行第 $c$ 列的格子。
最初，有 $k$ 张牌叠放在 $(1,1)$ 的位置上，这 $k$ 张牌每一张都有一个整数，这 $k$ 个整数是 $k$ 的一个全排列($1$~$k$)。其它单元格都是空的。
现在，你需要移动这些牌，使得 $(n,m)$ 格子上的牌从上到下的序号为 $1$~$k$，移动的规则如下：
* 除了 $(1,1)$ 和 $(n,m)$ 外，其它格子最多只能放一张纸牌。
* 一张牌可以向相邻的四个区域移动(上、下、左、右)。
* 在格子 $(1,1)$ 上，只能从牌堆的顶端取牌，不能将其它格子的牌放在 $(1,1)$ 上面。
* 在格子 $(n,m)$ 上，只能将其它格子的牌放在放在它的顶端，不能将 $(n,m)$ 上的牌移动到其它格子。
给定 $n$，$m$，$k$，请你帮 $AC$ 狗判断此问题是否可解。
最初，有 $k$ 张牌叠放在 $(1,1)$ 的位置上，这 $k$ 张牌每一张都有一个整数，这 $k$ 个整数是 $k$ 的一个全排列($1$~$k$)。其它单元格都是空的。
现在，你需要移动这些牌，使得 $(n,m)$ 格子上的牌从上到下的序号为 $1$~$k$，移动的规则如下：
* 除了 $(1,1)$ 和 $(n,m)$ 外，其它格子最多只能放一张纸牌。
* 一张牌可以向相邻的四个区域移动(上、下、左、右)。
* 在格子 $(1,1)$ 上，只能从牌堆的顶端取牌，不能将其它格子的牌放在 $(1,1)$ 上面。
* 在格子 $(n,m)$ 上，只能将其它格子的牌放在放在它的顶端，不能将 $(n,m)$ 上的牌移动到其它格子。
给定 $n$，$m$，$k$，请你帮 $AC$ 狗判断此问题是否可解。
输入格式
每个测试包含多个测试用例。
第一行包含一个整数 $T$ ($1 \le T \le 100$) — 表示测试用例的数量。
每个测试用例的第一行包含三个整数 $n$，$m$ 和 $k$ ($3 \le n,m \le 10^3$，$1 \le k \le 10^5$) — 棋盘的大小和牌的数量。
测试用例的第二行包含 $k$ 个整数，代表写在纸牌上的数字，从左往右顺序是最初格子 $(1,1)$ 上牌堆按顺序从顶端到底部的牌。
第一行包含一个整数 $T$ ($1 \le T \le 100$) — 表示测试用例的数量。
每个测试用例的第一行包含三个整数 $n$，$m$ 和 $k$ ($3 \le n,m \le 10^3$，$1 \le k \le 10^5$) — 棋盘的大小和牌的数量。
测试用例的第二行包含 $k$ 个整数，代表写在纸牌上的数字，从左往右顺序是最初格子 $(1,1)$ 上牌堆按顺序从顶端到底部的牌。
输出格式
对于每个测试用例，如果有解则输出
YES，否则输出 NO。输入输出样例
输入 #1
4 3 3 6 3 6 4 1 2 5 3 3 10 1 2 3 4 5 6 7 8 9 10 5 4 4 2 1 3 4 3 4 10 10 4 9 3 5 6 8 2 7 1
输出 #1
YES NO YES YES
第一个样例中：
将写有 $3$ 的卡片（$1$,$1$）->（$1$,$2$）->（$1$,$3$）。
将写有 $6$ 的卡片（$1$,$1$）->（$2$,$1$）->（$3$,$1$）-> （$3$,$2$）->（$3$,$3$）。
将写有 $4$ 的卡片（$1$,$1$）->（$1$,$2$）。
将写有 $1$ 的卡片（$1$,$1$）->（$2$,$1$）->（$2$,$2$）->（$2$,$3$）。
将写有 $2$ 的卡片（$1$，$1$）->（$2$，$1$）->（$2$、$2$）。
将写有 $5$ 的卡片（$1$,$1$）->（$2$,$1$）->（$3$,$1$）->（$3$,$2$）->（$3$,$3$）。
将写有 $2$ 的卡片（$2$,$2$）->（$2$,$1$）。
将写有 $4$ 的卡片（$1$,$2$）->（$2$,$2$）->（$3$,$2$）->（$3$，$3$）。
将写有 $3$ 的卡片（$1$,$3$）->（$1$,$2$）->（$2$,$2$）->（$3$,$2$）->（$3$，$3$）。
将写有 $2$ 的卡片（$2$,$1$）->（$3$,$1$）->（$3$,$2$）->（$3$，$3$）。
将写有 $1$ 的卡片（$2$,$3$）->（$3$,$3$）。
至此，$(3,3)$ 格子上的牌堆从上到下依次为 $1$ ~ $k$。
将写有 $3$ 的卡片（$1$,$1$）->（$1$,$2$）->（$1$,$3$）。
将写有 $6$ 的卡片（$1$,$1$）->（$2$,$1$）->（$3$,$1$）-> （$3$,$2$）->（$3$,$3$）。
将写有 $4$ 的卡片（$1$,$1$）->（$1$,$2$）。
将写有 $1$ 的卡片（$1$,$1$）->（$2$,$1$）->（$2$,$2$）->（$2$,$3$）。
将写有 $2$ 的卡片（$1$，$1$）->（$2$，$1$）->（$2$、$2$）。
将写有 $5$ 的卡片（$1$,$1$）->（$2$,$1$）->（$3$,$1$）->（$3$,$2$）->（$3$,$3$）。
将写有 $2$ 的卡片（$2$,$2$）->（$2$,$1$）。
将写有 $4$ 的卡片（$1$,$2$）->（$2$,$2$）->（$3$,$2$）->（$3$，$3$）。
将写有 $3$ 的卡片（$1$,$3$）->（$1$,$2$）->（$2$,$2$）->（$3$,$2$）->（$3$，$3$）。
将写有 $2$ 的卡片（$2$,$1$）->（$3$,$1$）->（$3$,$2$）->（$3$，$3$）。
将写有 $1$ 的卡片（$2$,$3$）->（$3$,$3$）。
至此，$(3,3)$ 格子上的牌堆从上到下依次为 $1$ ~ $k$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？