蠕虫游戏

模拟

【问题描述】

蠕虫是一个古老的电脑游戏，它有许多版本。但所有版本都有一个共同规则：操纵一条蠕虫在屏幕上转圈，并试着去避免撞到自己或障碍物。

这里我们将模拟一个简单的版本。游戏将在 50×50 的棋盘上进行，棋盘的左上角为(1,1)，蠕虫在初始时是一串 20 个相连的方格。所谓连接是指方格在水平或垂直方向上相接。蠕虫开始时是水平地伸展开的，从（25，11）到（25，30）。其中（25，30）是它的头。蠕虫只能向东（E），西（W），南（S），北（N）四个方向移动，但不能向自己移动，因此在开始时向西（W）是不允许的。每次移动时，蠕虫向给定的方向移动，一次只移动一格，并且保证它的长度不变。因此只有蠕虫的头和尾所占据的方格在移动一步后被改变。注意：蠕虫的头能移动到虫尾刚刚让出的空格。

你将被给定一系列移动指令并模拟虫的移动，直到：蠕虫撞上了自己；蠕虫越出了棋盘；蠕虫成功地完成了这些指令。在前两种情况下你应当忽略剩下的指令。

【输入】

每个输入文件包含了很多组数据。每个数据占 2 行，第一行是一个整数（n<100），表示移动指令的指令数（以 n=0 表示输入结束）；第 2 行包括了 n 个字符（E，W，S，N），字符之间没有空格，表示移动的指令。

【输出】

每个数据输出一行，格式为以下 3 种中的一种（m 是你要决定输出的步数）：

The worm ran into itself on move m.

The worm ran off the board on move m.

The worm successfully made all m moves.

【解题过程】

我用了一个数组来记录 20 个点的坐标。贪吃蛇移动一步可以当做是尾部的点消失并出现在头部，这样处理是最方便的。

初次提交 AC。

?

直角三角形

离散化

【问题描述】

平面上给定 n 个两两不同的整数点，统计以给定的点为顶点，其直角边平行于坐标轴的直角三角形的个数。

【输入】

输入文件第一行是一个整数 n。

以下 n 行，每行是一个点的坐标。

【输出】

输出一个整数，表示统计结果。

【输入样例】

4

0 0

0 1

1 0

1 1

【输出样例】

4

【数据规模】

30%的数据满足 n≤100；

50%的数据满足 n≤1000；

100%的数据满足 0<n≤100,000，所有坐标不超过 32 位整数范围。

【解题过程】

看到 10^6 就又想到排序了。

思路很明显：枚举直角顶点是哪一个，则能构成的直角三角形的数目=横坐标与它相同的点的数目*纵坐标与它相同的点的数目。

如何统计横纵坐标相同的点的数目？先按横坐标排序，横坐标相同的点必然排在一起，统计并记录到数组中。比如对于排序后第 7 个点有 3 个点的横坐标与其相同，就令 x[7] = 3. 再按纵坐标排序，然后计算。

初次提交 AC。

?

聪明的打字员

搜索

【问题描述】

阿兰是某机密部门的打字员，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0, Swap1, Up, Down, Left, Right。为了说明这六个键的作用，我们先定义录入区的 6 个位置的编号，从左至右依次为 1，2，3，4，5，6。下面列出每个键的作用：

Swap0：按 Swap0，光标位置不变，将光标所在位置的数字与录入区的 1 号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的 1 号位置，则按 Swap0 键之后，录入区的数字不变；

Swap1：按 Swap1，光标位置不变，将光标所在位置的数字与录入区的 6 号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的 6 号位置，则按 Swap1 键之后，录入区的数字不变；

Up：按 Up，光标位置不变，将光标所在位置的数字加 1（除非该数字是 9）。例如，如果光标所在位置的数字为 2，按 Up 之后，该处的数字变为 3；如果该处数字为 9，则按 Up 之后，数字不变，光标位置也不变；

Down：按 Down，光标位置不变，将光标所在位置的数字减 1（除非该数字是 0），如果该处数字为 0，则按 Down 之后，数字不变，光标位置也不变；

Left：按 Left，光标左移一个位置，如果光标已经在录入区的 1 号位置（左起第一个位置）上，则光标不动；

Right：按 Right，光标右移一个位置，如果光标已经在录入区的 6 号位置（左起第六个位置）上，则光标不动。

当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为 6 的初始密码，而且光标固定出现在 1 号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。

现在，阿兰有一个 6 位的数字密码，请编写一个程序，求出录入一个密码需要的最少的击键次数。

【输入】

仅一行，含有两个长度为 6 的数，前者为初始密码，后者为目标密码，两数间用空格隔开。

【输出】

仅一行，含有一个正整数，为最少需要的击键次数。

【输入样例】

123456 654321

【输出样例】

11

【解题过程】

丧心病狂的搜索题。

感觉 BFS 不太够，就想 A*。但是 h(x) 函数不好设计，如果 h(x) = 位置正确的数字个数，那么效果不好，对搜索没有太大的促进作用（甚至会因为优先队列的复杂度较大而劣于直接 BFS）；如果 h(x) = 每个位置上的数字与目标数字的差的绝对值之和，其实是错的，因为有 Swap 操作的存在使得可以一步让两个不同的数字到正确的位置，这样不满足 h(x)<=h*(x) 的要求。

那还是直接 BFS 吧。但对于极限数据 000000 999999 基本上没希望（5s+）。

第一次提交 70 分。

后来看题解看到一个剪枝：

• 如果当前数字已经等于目标状态中所有数字的最大值，就不执行 Up 操作；如果当前数字已经等于目标状态中所有数字的最小值，就不执行 Down 操作

后来想想这个剪枝是显而易见的，只能说做题的时候太浮躁了。

另外还要注意一下常数的优化。做这道题一般是把六个数字加上位置信息压成 7 位十进制数，而扩展状态的时候对于有些操作不必将 7 位数展开到数组里再操作，比如 Up 操作完全可以通过加上 10 的幂来改变某一位上的数字，这样会比拆分成数字再拼合成整数要快不少。

加了如上优化就能 AC 老师给的数据。

06day2