自动搬运

查看原文

来自洛谷，原作者为

	Augen_stern Du bist der ausschließliche Stern in meinen Augen. ||Du bist mein Augenstern. || 珍爱生命，远离 jcer

搬运于2025-08-24 21:30:38，当前版本为作者最后更新于2021-09-07 20:59:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1: 分析求解

题目的意思大致就是模拟一条蠕虫的活动，来观察它是否还活着。

算法的话直接暴力模拟就好了。

读题一直都很重要，请注意“棋盘的左上角为 $(1,1)$”和“蠕虫开始时是水平地伸展开的，从 $(25,11)$ 到 $(25,30)$”，所以定义两个方向数组时注意 $(x,y)$ 中的 $x$ 实际上是原直角坐标系的 $y$，这里的 $y$ 与其同理；

为了方便叙述，本文 $(x,y)$ 中的 $x$ 实际上是纵坐标，$y$ 实际上是横坐标（有点绕）

所以可以定义操作数组：

int dx[7]= {0,-1,0,1,0}; 
int dy[7]= {0,0,1,0,-1}; // 占位，N，E，S，W；

接着考虑第一种问题：“蠕虫撞上了自己”；

此时，我们可以通过两个数组分别来定义这个蠕虫的每一个身体节点，为每一个头，而因为这只蠕虫的长度恒为 $20$，所以它的尾节点则可以储存在身体节点数组中。

预处理初始的身体节点：

int cnt=0,fg=0;
for(int i=11; i<=30; i++) {
	headx[i-10]=25;
	heady[i-10]=i;
	map[25][i]=1; // 标记每一个身体节点。
	cnt++;
}
int len=cnt;

在对于输入的字符串的每一位进行存储：

int f=0;
if(s[i]=='N') f=1;
else if(s[i]=='E') f=2;
else if(s[i]=='S') f=3;
else if(s[i]=='W') f=4;
cnt++;
headx[cnt]=headx[cnt-1]+dx[f];
heady[cnt]=heady[cnt-1]+dy[f];
tailx=headx[cnt-len+1];
taily=heady[cnt-len+1]; // len=20;
map[tailx][taily]=0; // 释放过去的尾巴标记。

此时，若蠕虫撞上了自己，则可以有：

if(map[headx[cnt]][heady[cnt]]==1) printf("The worm ran into itself on move %d.\n",i+1),fg=1;

然后考虑第二个问题，蠕虫出界了：

if(headx[cnt]>50||heady[cnt]>50||headx[cnt]<1||heady[cnt]<1) printf("The worm ran off the board on move %d.\n",i+1),fg=1;

这些时候，因为标记 $fg=1$ 则可以直接下一组数据，跳出循环。

直到最后还活着，就可以成功了：

if(fg) continue;
printf("The worm successfully made all %d moves.\n",n);

Part 2：CODE

所以就可以秒掉了，只需要注意每一次循环都要初始化：

#include<iostream>
#include<math.h>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 0x7fffffff/2
using namespace std;
int n,tailx,taily;
int map[55][55];
int dx[7]= {0,-1,0,1,0};
int dy[7]= {0,0,1,0,-1};
int headx[200],heady[200];
int main() {
	while(scanf("%d",&n)) {
		if(n==0) break;
		memset(map,0,sizeof(map));
		memset(headx,0,sizeof(headx));
		memset(heady,0,sizeof(heady)); // 初始化；
		int cnt=0,fg=0;
		for(int i=11; i<=30; i++) {
			headx[i-10]=25;
			heady[i-10]=i;
			map[25][i]=1;
			cnt++;
		}
		int len=cnt; // 预处理；
		string s;
		cin>>s;
		for(int i=0; i<n; i++) {
			int f=0;
			if(s[i]=='N') f=1;
			else if(s[i]=='E') f=2;
			else if(s[i]=='S') f=3;
			else if(s[i]=='W') f=4; // 找方向；
			cnt++;
			headx[cnt]=headx[cnt-1]+dx[f];
			heady[cnt]=heady[cnt-1]+dy[f];
			tailx=headx[cnt-len+1];
			taily=heady[cnt-len+1]; // 储存节点；
			map[tailx][taily]=0;
			if(map[headx[cnt]][heady[cnt]]==1) printf("The worm ran into itself on move %d.\n",i+1),fg=1; // 第一种情况；
			else if(headx[cnt]>50||heady[cnt]>50||headx[cnt]<1||heady[cnt]<1) printf("The worm ran off the board on move %d.\n",i+1),fg=1; // 第二种情况；
			else map[headx[cnt]][heady[cnt]]=1;
			if(fg) break;
		}
		if(fg) continue; // 直接下一组数据。
		printf("The worm successfully made all %d moves.\n",n); // 苟到最后就是胜利。
	}
	return 0;
}

自给自足，丰衣足食！！！

2021.9.8 13:20 初稿成