关门捉贼
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
小敌困之。剥,不利有攸往。
题目描述
33DAI 发现有 只小猫在 的二维数组里,第 只小猫在第 行的第 列(保证 ),可能有多只小猫在同一个位置。
已知每只小猫都只会往上下左右四个方向直线行走,不会拐弯。33DAI 可以在某些位置放稻草人来拦住小猫。稻草人必须放在 的二维数组内,且不能放在已经有小猫或稻草人的位置。请帮 33DAI 构造一个放稻草人的方案。
形式化的说,如果在
- 第 行的第 列
- 第 行的第 列
- 第 列的第 行
- 第 列的第 行
这四个区域都分别至少放了一个稻草人,就可以拦住第 只小猫。
输入格式
第一行两个整数 。
接下来 行,第 行为两个整数 。
输出格式
显然不可能无解,最多 个稻草人肯定能拦住所有小猫,如果有多解,输出任意一种即可。
第一行需要输出一个 范围内的整数 ,表示需要放 个稻草人。
接下来 行,第 行为第 个稻草人的位置 ,即放在第 行的第 列。
3 5
2 2
2 4
4 4
7
1 2
1 4
2 1
2 5
4 2
4 5
5 4
输出为一种可能的方案,下面是这个方案放稻草人的位置
数据规模与约定
对于 的数据,,,。
- 子任务 1(10 分):保证 。
- 子任务 2(20 分):保证 。
- 子任务 3(30 分):保证 。
- 子任务 4(40 分):没有特殊限制。