P1815 蠕虫游戏

· · 题解

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 初稿成