题目背景

NOIP2018原创模拟题 T3

NOIP DAY1 T3 or DAY 2 T2 难度

贪吃蛇大家都玩过吧，当然不同版本有不同规则。下面介绍PION贪吃蛇。

注意：测试点#4,#5错误已修改，感谢：@EnTaroTassadar,@天道

题目描述

【题解】洛谷U38098[NOIP2018原创模拟赛DAY1T3]PION贪吃蛇模拟
表示方法：
该题中贪吃蛇存在于一个 $n$ 行 $m$ 列的矩形中，用 ‘.’ 表示空地，用 '#’ 表示蛇身，用 ‘@’表示蛇头，用‘&’表示食物例如：图一表示 $5*6$ 的矩形，有一条蛇，蛇长度为 $7$ ，有两个食物

基本规则：
1.蛇头每一秒就会移动一格，身体自然会跟着移动，用W表示向上，S表示向下，A表示向左，D表示向右

2.蛇每吃一个食物就长度就会加一，而增加的长度体现在食物所在的地方，你可以把吃食物理解成食物变成了蛇头，之前的蛇头变成了蛇身，这一秒不移动

例如：图二的三幅图展示了第一秒，第二秒，和第三秒的情况

3.蛇如果死亡，身体（包括头）一定会全部变成食物

4.PION贪吃蛇的蛇头碰到自己或别的蛇的身体就会死亡

例如：图三的三幅图展示了第二条蛇撞在别人身体上死亡的过程

5.蛇头撞在边界上也会引起死亡，但蛇头刚好现在边界上不会

例如：图四第二幅图虽然蛇头在边界上，但是只是刚好，如果此时进行D操作蛇就会死亡，如果进行W或S就不会

6.如果有操作使蛇头向相反方向运动，之后如果与身体重合蛇也会死亡（比如：图二第一幅图使用A操作,蛇就会死亡，此时在原地成为三个食物，你也可以理解为蛇下一秒不行动而自杀了）

7.两条蛇蛇头相撞，主动撞上的死亡

8.蛇的移动按编号由小到大进行（编号的含义见下文）

输入输出格式

输入格式：

第一行两个数 $n,m,k$ 表示 $n*m$ 的矩形， $k$ 表示操作次数

接下来 $n$ 行每行 $m$ 个字符，表示地图

再接下来 $c$ 行（注意：图中有几条蛇就有几行），每行 $k$ 个字符，表示有 $k$ 个操作（如果执行了某个操作蛇死了，就忽略后面的操作）

我们将蛇编号：按每条蛇蛇头的坐标从小到大编号为 $1,2,\cdots,c$ （越靠近上边的坐标越小，如果相同越靠近左边的坐标越小）

例如：图三第一幅图两条蛇的蛇头坐标分别为 $(4,3)$ ， $(3,7)$ 所以较长的蛇编号为 $2$ ，较短的蛇编号为 $1$

输出格式：

$c+1$ 行，输出 $k$ 次操作后每一条蛇的长度，编号；每一行第一个为长度，第二个数为编号

最后一行输出剩下食物的总个数

注意：输出按长度由大到小排序（长度相同按编号由小到大排序），死亡的蛇长度为 $0$

输入输出样例

输入样例#1：

5 7 6
.&…&.
…##@…
.&…&.
…##@…
.&…&.
DWAAAA
WDDDDD

输出样例#1：

5 1
0 2
7

输入样例#2：

9 9 4
…
.#######.
…#.
[email protected]#.&@.#.
&.#.&&.#.
&&######.
.&…
…@####…
…
ASSD
ASDD
WASD

输出样例#2：

22 1
4 2
0 3
6

说明

样例说明：

【题解】洛谷U38098[NOIP2018原创模拟赛DAY1T3]PION贪吃蛇模拟

图五，图六展示了从第0秒开始之后每一秒地图的状态，请看图理解（样例二图四有点小错误）

数据范围：

$10\%$ 数据满足 $n,m\leq5,c=1,k\leq3$

$30\%$ 数据满足 $n,m\leq10,c\leq2,k\leq5$

$50\%$ 数据满足 $n,m\leq50,c\leq5,k\leq20$

$70\%$ 数据满足 $n,m\leq100,c\leq7,k\leq50$

$100\%$ 数据满足， $n,m\leq200,c\leq20,k\leq100$ ，且图中的蛇不会引起混淆

输入保证图中没有蛇会像这样难以判断：

.#.
##@
#.#
@##

其实就是按照题目要求进行模拟。当时写了份代码只有60分。

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
char s[2100];
int n,m,k,flag,c,num,nxtx[]={1,-1,0,0},nxty[]={0,0,1,-1},vis[100100],cnt,idx[2100][2100];
struct node{
	int x,y,kind;
}p[100100];
struct Snake{
	int len,id;
	deque<int>dq;
	bool operator<(const Snake&rhs)const{
	return len>rhs.len||(len==rhs.len&&id<rhs.id);}
}snake[500];
void bfs(int pos)
{
	queue<int>q;while(q.size())q.pop();
	snake[c].len=1;snake[c].id=c;q.push(pos);vis[pos]=1;snake[c].dq.push_back(pos);p[pos].kind=2;
	while(q.size())
	{
		int tmp=q.front();q.pop();
		int x=p[tmp].x,y=p[tmp].y;
		for(int i=0;i<4;i++)
		{
			int nx=x+nxtx[i],ny=y+nxty[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[idx[nx][ny]]&&p[idx[nx][ny]].kind==2)
			{
				q.push(idx[nx][ny]);vis[idx[nx][ny]]=1;snake[c].len++;snake[c].dq.push_back(idx[nx][ny]);
			}
		}
	}
}
void des(int id)
{
	while(snake[id].dq.size())
	{
		int pos=snake[id].dq.front();snake[id].dq.pop_front();
		p[pos].kind=3;cnt++;
	}
	snake[id].len=0;
}
int work(int id,int nx)
{
	int pos=snake[id].dq.front();
	int x=p[pos].x+nxtx[nx],y=p[pos].y+nxty[nx];
	if(x<0||x>n||y<0||y>m)
	{
		des(id);return 0;
	}
	if(p[idx[x][y]].kind==2)
	{
		des(id);return 0;
	}
	if(p[idx[x][y]].kind==3)
	{
		p[idx[x][y]].kind=2;
		snake[id].len++;cnt--;snake[id].dq.push_front(idx[x][y]);return 1;
	}
	p[idx[x][y]].kind=2;snake[id].dq.push_front(idx[x][y]);p[snake[id].dq.back()].kind=0;snake[id].dq.pop_back();return 1;
}
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)
		{
			idx[i][j]=++num;
			p[num].x=i;p[num].y=j;
			switch(s[j]){
				case '.':p[num].kind=0;break;
				case '@':p[num].kind=1;break;
				case '#':p[num].kind=2;break;
				case '&':p[num].kind=3;cnt++;break;
			}
		}
	}
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	        if(p[idx[i][j]].kind==1)c++,bfs(idx[i][j]);
	for(int i=1;i<=c;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=k;j++)
		{
			switch(s[j])
			{
				case 'W':flag=work(i,1);break;
				case 'A':flag=work(i,3);break;
				case 'S':flag=work(i,0);break;
				case 'D':flag=work(i,2);break;
			}
			if(!flag)break;
		}
	}
	sort(snake+1,snake+c+1);
	for(int i=1;i<=c;i++)printf("%d %d\n",snake[i].len,snake[i].id);
	printf("%d\n",cnt);
	return 0;
}

后来也就没有改这份代码，重新写了一份。

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,k,c,hd[25][2],mp[210][210],len[25],cnt;
int dx[]={1,0,0,-1},dy[]={0,-1,1,0};
char a[210][210];
string cmd[25];
struct node{
	int x,y;
	node(){}
	node(int _x,int _y):x(_x),y(_y){}
};
struct Snake{
	int id,len;
	bool operator<(const Snake&rhs)const{
	return len>rhs.len||(len==rhs.len&&id<rhs.id);}
}s[25];
queue<node>body[25];
void dfs(int i,int j)
{
	if(!mp[i][j]&&(a[i][j]=='#'||(a[i][j]=='@'&&len[c]==0)))
	    mp[i][j]=c,len[c]++;
	else return;
	for(int k=0;k<4;k++)
	    dfs(i+dx[k],j+dy[k]);
	body[c].push(node(i,j));
}
void die(int id)
{
	len[id]=0;
	while(body[id].size())
	{
		node tmp=body[id].front();body[id].pop();
		mp[tmp.x][tmp.y]=-1;
	}
}
void Move(int i,int j,int id,int cas)
{
	int x=i+dx[cas],y=j+dy[cas];
	if(x<1||x>n||y<1||y>m||mp[x][y]>0)
	{
		die(id);
		return;
	}
	if(mp[x][y]==-1)
	{
		len[id]++,mp[x][y]=id;
		hd[id][0]=x,hd[id][1]=y;
		body[id].push(node(x,y));
	}
	else
	{
		mp[x][y]=id,hd[id][0]=x,hd[id][1]=y;
		body[id].push(node(x,y));
		node tmp=body[id].front();body[id].pop();
		mp[tmp.x][tmp.y]=0;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	        cin>>a[i][j];
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	        if(a[i][j]=='@')
	            c++,dfs(i,j),hd[c][0]=i,hd[c][1]=j;
	        else if(a[i][j]=='&')
	            mp[i][j]=-1;
	for(int i=1;i<=c;i++)
	    cin>>cmd[i];
	for(int i=0;i<k;i++)
	    for(int j=1;j<=c;j++)
	        if(len[j])
	        {
	        	switch(cmd[j][i])
	        	{
	        		case 'W':Move(hd[j][0],hd[j][1],j,3);break;
	        		case 'A':Move(hd[j][0],hd[j][1],j,1);break;
	        		case 'S':Move(hd[j][0],hd[j][1],j,0);break;
	        		case 'D':Move(hd[j][0],hd[j][1],j,2);break;
				}
			}
	for(int i=1;i<=c;i++)
	    s[i].id=i,s[i].len=len[i];
	sort(s+1,s+c+1);
	for(int i=1;i<=c;i++)
	    cout<<s[i].len<<" "<<s[i].id<<endl;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	        if(mp[i][j]==-1)
	            cnt++;
	cout<<cnt<<endl;
	return 0;
}

总结

放到T3的大模拟确实让我感觉有点惊讶。不过感觉也不是那么难写，至少部分分是有的。

【题解】洛谷U38098[NOIP2018原创模拟赛DAY1T3]PION贪吃蛇 模拟