Luogu P4944 【PION贪吃蛇】

简单模拟题

用一个数据结构存储这条蛇

考虑蛇的移动

1，如果死了，就把整个蛇清空，所有位置标记为食物

2，如果吃了东西，把这个位置更新为蛇头

3，如果正常走路，这个位置设为蛇头，同时删掉尾巴

蛇的存储？观察到我们涉及的所有操作，双端队列无疑是$The~~Best~~Choice$

#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
//q.front -> head
//q.back -> tail
//mp{
// 0 -> square ; 1 -> edge ; 2-> food
//}
const int dx[]={1,-1,0,0};
const int dy[]={0,0,-1,1};
struct pos{
    int x,y;
};
struct length{
    int id,len;
}ans[30];
map<char,int>to;
deque<pos>sk[30];
int n,m,k,mp[210][210],cnt;
char s[210][210],op[30][110];
void bfs(int id,int x,int y)
{
    queue<pos>q;
    q.push((pos){x,y});
    while(!q.empty())
    {
        pos u=q.front();
        sk[id].push_back(u);
        mp[u.x][u.y]=1;
        q.pop();
        for(int i=0;i<4;i++)
        {
            pos th;
            th.x=u.x+dx[i];
            th.y=u.y+dy[i];
            if(s[th.x][th.y]=='#')
                q.push(th),s[th.x][th.y]='.';
        }
    }
}
void work(int x)
{
    for(int i=1;i<=cnt;i++)
    {
        if(!sk[i].size())
            continue;
        pos th;
        th.x=sk[i].front().x+dx[to[op[i][x]]];
        th.y=sk[i].front().y+dy[to[op[i][x]]];
        if(mp[th.x][th.y]==2)
            sk[i].push_front(th),mp[th.x][th.y]=1;
        else if(mp[th.x][th.y]==1)
            while(!sk[i].empty())
            {
                mp[sk[i].front().x][sk[i].front().y]=2;
                sk[i].pop_front();
            }
        else
        {
            mp[sk[i].back().x][sk[i].back().y]=0,mp[th.x][th.y]=1;
            sk[i].push_front(th),sk[i].pop_back();
        }
    }
}
bool cmp(const length &x,const length &y)
{
    return x.len==y.len?x.id<y.id:x.len>y.len;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    to['W']=1,to['S']=0,to['A']=2,to['D']=3;
    for(int i=1;i<=n;i++)
        mp[i][0]=mp[i][m+1]=1;
    for(int i=1;i<=m;i++)
        mp[0][i]=mp[n+1][i]=1;
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(s[i][j]=='&')
                mp[i][j]=2;
            else if(s[i][j]=='@')
                bfs(++cnt,i,j);
    for(int i=1;i<=cnt;i++)
        scanf("%s",op[i]+1);
    for(int i=1;i<=k;i++)
        work(i);
    for(int i=1;i<=cnt;i++)
        ans[i].len=sk[i].size(),ans[i].id=i;
    sort(ans+1,ans+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
        printf("%d %d
",ans[i].len,ans[i].id);
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]==2)
                res++;
    printf("%d
",res);
    return 0;
}