← 返回题目列表

Codeforces · 43/D

D. 旅程

中文机器翻译题面 查看原题

Berland 的领土由大小为 n × m 的矩形区域表示。 Berland国王住在首都,位于左上方的广场(1, 1)。右下方块的坐标为 (n, m)。有一天,国王决定走遍整个国家,然后返回首都,他把每个广场(首都除外)都逛了一遍。国王必须恰好访问首都两次,一次是在旅程的起点和终点。国王只能移动到相邻的方格。然而,王室顾问表示,国王可能无法做到这一点。但还有一条出路——可以在一些方格之间建立单向传送系统,这样国王就可以实现他的计划。一个方块上只能安装一个传送器,每个传送器可以使用任意次数,但是每次使用时,它都会传送到任何单个传送器方块的相同位置。当国王到达安装有传送器的广场时,他可以自行选择是否使用传送器。国王需要安装多少个传送器才能完成旅程?您还应该为国王制定旅行路径。

输入

第一行包含两个以空格分隔的整数 n 和 m (1 ≤ n, m ≤ 100, 2 ≤ n · m) — 字段大小。左上方块的坐标为 (1, 1),右下方块的坐标为 (n, m)。

输出

在第一行输出整数 k — 传送器的最小数量。然后输出 k 行,每行包含 4 个整数 x1 y1 x2 y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m)——安装传送器的方格的坐标 (x1, y1),以及传送器引导的方格的坐标 (x2, y2)。

然后打印 nm + 1 行,每行包含 2 个数字——按照国王访问方块的顺序排列的坐标。行进路径的起点和终点必须为 (1, 1)。国王可以移动到旁边的方格和传送器引导的方格。此外,他还应该访问首都两次,并且他应该访问其他广场一次。

示例

输入 #1

2 2

输出 #1

0
1 1
1 2
2 2
2 1
1 1

输入 #2

3 3

输出 #2

1
3 3 1 1
1 1
1 2
1 3
2 3
2 2
2 1
3 1
3 2
3 3
1 1