本蒟蒻的第三篇题解！

题目传送门

P1815

解法

巨简单的一道模拟题。（我才不会告诉你我卡了五次才对呢）

虽然可以直接按照题意模拟，但是我们可以使用一个技巧：

每次把蠕虫的尾巴丢到它的头前面。

使用这个方法，模拟起来较简单，还可以节省时间。

为什么可以这样做呢？来，我们上图。

如图，模拟一个 $4*4$ 的棋盘，和一条长度为 $4$ 的蠕虫，头在最右边。

我们往南移之后，会变成这样：

正常模拟是一个一个身体地移动，但是，你会发现，这就相当于把尾巴丢到头部的南边，再把尾巴变成新的头。（东、西、北同理）

题目里面有一句话，大家都可能会有些不了解：蠕虫的头能移动到虫尾刚刚让出的空格。

我给你们举个例子就明白了：

（黄色的是虫头，箭头是虫子要移动的方向）

就像这样，虫子像指定方向移动时，虫尾就会刚好让出一个空格，虫头就可以移到空格上。

然后就变成了这样：

如果我们用刚刚的方法，就应该把虫尾丢到虫头前面，也就是原来的位置，再把它变成虫头，你就会发现，这样完全没问题，还不用考虑移动和检查的顺序。（具体的实现在代码中）

打代码的时候，要注意的有几点：

1. 建议将每一个过程单独定义一个函数，方便 debug。

2. 判断是否超出边界的时候很容易被坑（详见下方我的代码）

3. 判断相撞的时候根本不用开二维数组，只需要把头部坐标和其他的身体坐标进行比较就行了，也不需要把身体和身体进行比较。

4. 判断相撞和出界的时候，不用管身体，因为，身体走过的地方，头都在之前走过了。

代码

#include <bits/stdc++.h>
#define str string

using namespace std;

int n, mx[4] = {1, -1, 0, 0}, my[4] = {0, 0, -1, 1}, chk;
str st;
char c;
struct node{ // 一截身体
	int x, y;
	bool operator==(const node &a){
		return x == a.x && y == a.y; // 等于号的重载，判断坐标是否重合
	}
}s[20]; // 定义蠕虫，头是 s[0]，尾是 s[19]
void start(){ // 身体初始化
	for (int i = 0;i < 20;i ++) s[i].y = 25, s[i].x = 30 - i;
}
void move(int t){ // 移动
	s[19].x = s[0].x + mx[t], s[19].y = s[0].y + my[t]; // 把尾巴丢到头前面
	for (int i = 19;i > 0;i --) swap(s[i], s[i - 1]); // 排序，头放在最前
}
int check(){
	for (int i = 1;i < 20;i ++){
		if (s[0] == s[i]) return 1; // 碰撞
	}
	if (s[0].x > 50 || s[0].x < 1 || s[0].y > 49 || s[0].y < 1) /*注意这里是重点！如果打成>50，会出现26步才出界*/ return 2; // 出界
	return 0; // 正常运作
}

int main(){
	while (1){
		cin >> n;
		if (n == 0) break;
		start(); // 初始化虫子
		cin >> st;
		for (int i = 1;i <= n;i ++){
			c = st[i - 1];
			if (c == 'E') move(0);
			if (c == 'W') move(1);
			if (c == 'S') move(2);
			if (c == 'N') move(3); // 移动
            		chk = check(); // 检查
	        	if (chk){
	        		if (chk == 1) printf("The worm ran into itself on move %d.\n", i); // 撞到自己
	        		if (chk == 2) printf("The worm ran off the board on move %d.\n", i); // 出界
				break; // 忽略剩下的
			}
		}
		if (!chk) printf("The worm successfully made all %d moves.\n", n); // 成功
	}
}

两个小时才 AC。。。

某些灵感来源于 @sxyugao 和 @江河之北