A7400 | 探索
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
> 黄色的树林里分出两条路 / 可惜我不能同时去涉足
> 我在那路口久久伫立 / 我向着一条路极目望去 / 直到它消失在丛林深处
>
> 但我却选了另外一条路 / 它荒草萋萋，十分幽寂 / 显得更诱人，更美丽
> 虽然在这条小路上 / 很少留下旅人的足迹
>
> 那天清晨落叶满地 / 两条路都未经脚印污染 / 啊，留下一条路等改日再见
> 但我知道路径延绵无尽头 / 恐怕我难以再回返
>
> 也许多少年后在某个地方 / 我将轻声叹息将往事回顾
> 一片树林里分出两条路 / 而我选择了人迹更少的一条 / 从此决定了我一生的道路
>
> ——义务教育教科书语文人教版七年级下册《未选择的路》
> 如果有第二次机会，你还会再选择 OI 吗？
Minecraft 的地图由 $n\times m$ 个区块组成，我们将每个区块看成一个大小为 $1\times1$ 的方格，形成了一个 $n$ 列 $m$ 行的网格。其中最左下角的点坐标为 $(0,0)$，最右上角的点坐标为 $(n,m)$。Steve 最初站在 $(0,0)$ 的位置，最终要回到基地 $(x,y)$。他每一次移动可以沿某个区块的对角线移动，并称他探索过了这个区块。
请你求出，在不离开地图并只探索每个区块至多一次的前提下，Steve 最多能够探索几个区块。特别地，若他根本无法回到 $(x,y)$，输出
-1。同时每组测试数据还会给定一个参数 $q$，若 $q=1$ 且答案不是 -1，你需要构造出任意一种可行的方案。输入格式
*每个测试点包含多组测试数据**。输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据的组数。对于每组测试数据：
第一行包含五个正整数 $n,m,x,y,q$，分别表示地图的大小、基地的位置和该组测试数据的参数。
第一行包含五个正整数 $n,m,x,y,q$，分别表示地图的大小、基地的位置和该组测试数据的参数。
输出格式
本题采用 Special Judge。你只需要输出任意一种符合条件的方案。
对于每组测试数据：
第一行输出一个整数 $k$，表示 Steve 最多能够探索的区块数，若他根本无法回到 $(x,y)$，输出
若 $q=1$ 且答案不是
对于每组测试数据：
第一行输出一个整数 $k$，表示 Steve 最多能够探索的区块数，若他根本无法回到 $(x,y)$，输出
-1。若 $q=1$ 且答案不是
-1，则继续输出 $k$ 行，其中的第 $i$ 行包含两个整数 $x_i,y_i$，代表第 $i$ 次移动后 Steve 所在位置的坐标。输入输出样例
输入 #1
0 10 2 2 2 2 1 2 3 0 2 1 3 3 3 3 0 3 5 2 4 0 4 4 0 4 0 4 5 3 5 0 4 5 4 0 0 5 5 4 2 0 6 4 6 4 0 6 6 2 3 1
输出 #1
2 1 1 2 2 4 1 1 2 2 1 3 0 2 9 14 12 15 20 22 18 -1
【样例解释】
对于第二组测试数据，地图大小为 $2\times 3$，基地坐标为 $(0,2)$。可以证明 Steve 最多只能探索 $4$ 个区块。样例输出所对应的移动方案为 $(0,0)\to(1,1)\to(2,2)\to(1,3)\to(0,2)$。
【数据范围】
* 特殊性质 $\text{A}$：$n=m$。
* 特殊性质 $\text{B}$：$x=n,y=m$。
* 特殊性质 $\text{C}$：$n,m$ 都是奇数。
* 特殊性质 $\text{D}$：$q=0$。
对于 $100\%$ 的测试点，保证：$1\le T\le 10^5$，$1 \le n,m \le 10^9$，$0\le x\le n$，$0\le y\le m$，$q\in\{0,1\}$，单个测试点中所有测试数据的 $q\times n\times m$ 之和不超过 $5\times10^5$。
对于第二组测试数据，地图大小为 $2\times 3$，基地坐标为 $(0,2)$。可以证明 Steve 最多只能探索 $4$ 个区块。样例输出所对应的移动方案为 $(0,0)\to(1,1)\to(2,2)\to(1,3)\to(0,2)$。
【数据范围】
| 测试点编号 | 特殊性质 |
|---|---|
| $1$ | $\text{ABC}$ |
| $2$ | $\text{ABD}$ |
| $3$ | $\text{AB}$ |
| $4$ | $\text{BC}$ |
| $5$ | $\text{BD}$ |
| $6$ | $\text{B}$ |
| $7$ | $\text{C}$ |
| $8$ | $\text{D}$ |
| $9-10$ | 无 |
* 特殊性质 $\text{A}$：$n=m$。
* 特殊性质 $\text{B}$：$x=n,y=m$。
* 特殊性质 $\text{C}$：$n,m$ 都是奇数。
* 特殊性质 $\text{D}$：$q=0$。
对于 $100\%$ 的测试点，保证：$1\le T\le 10^5$，$1 \le n,m \le 10^9$，$0\le x\le n$，$0\le y\le m$，$q\in\{0,1\}$，单个测试点中所有测试数据的 $q\times n\times m$ 之和不超过 $5\times10^5$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？