You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

4 个子任务 problem.pdf

sample.rar

梦中超越

问题描述

时限:4000ms

还有一年就要读研究生了，运动完后，Snakes 决定去看一会儿书，为科研做准备。

书上写着，asml EUV光刻机很小，中国造不出来。看完这几个字，Snakes 陷入了沉睡。

光刻机，最难的就是光源，既然小的光源很难造，就造一个大的光源吧。

由此，Snakes 在梦里解决了卡脖子问题。顺带地，有这样一道题目。

我们需要引导光从 $A$ 点移动到 $B$点，题目抽象如下：

在一平面直角坐标系上有 $k$ 个点，$1$ 是起点，坐标为(1,1)， $k$是终点，坐标为$(n,m)$。

第 $i$ 个点的坐标 $(x_i,y_i)$，保证 $1\le x_i \le n, 1 \le y_i \le m$。

激光从 $i$ 号点到 $j$ 号点传输时间为 $2^{max(|x_i-x_j|,|y_i-y_j|)}$。

试求，从 $1$ 号点到 $k$ 号点的最短传输时间，并给出一组方案。

输入格式

第一行三个整数 $n,m,k$。

接下来 $k$ 行，每行两个整数 $x_i,y_i$，表示点的坐标。

输出格式

输出 $len$ 行，表示最快的方案中经过多少个点。

第二行 $len$ 个数，表示依次经过的点。

如果有多种方案，输出任意一种即可。

4 5 3
1 1
2 3
4 5

3
1 2 3

5 6 9
1 1
4 3
4 6
2 5
3 1
3 3
3 6
5 4
5 6

5
1 6 2 8 9

数据范围与评分

子任务 1（$20\%$）：$2\leq n,m,k\leq 20$。

子任务 2（$20\%$）：$2\leq n,m,k\leq 500$。

子任务 3（$30\%$）：$2\leq n,m,k \leq 10000$， 每行每列只有一个点。

子任务 4（$30\%$）：$2\leq n,m,k \leq 10000$。