P4944 PION贪吃蛇题解

Wy_x · 2023-06-12 20:22:42 · 题解

题目传送门：P4944 PION贪吃蛇

题目描述：

有一个 n \times m 的字符矩阵，其中，用 . 表示空地，用 # 表示蛇身，用 @ 表示蛇头，用 & 表示食物。

对于每条蛇，有 k 个操作，操作时需要遵守 8 条基本规则。

操作完后，按顺序（题目的输出格式中有描述）输出蛇的长度和编号。

最后，输出食物总个数。

蛇身的存储：

输入地图时：
1. 对于任意蛇头，最多只有一块蛇身于其相连（可以只有一个蛇头），且蛇身最多为二连块。
2. 输入数据保证图中的蛇均可以判断身体与头的对应关系，不会造成蛇身形态多解。
操作中：
1. 可能会出现一个蛇头与多个蛇身相连，或蛇身出现环的情况。此时，在地图上模拟已无法满足要求，可以用队列存储蛇身。
2. 操作时可能会在队列前加点（蛇头走到了一个有食物的格子里，原来的蛇头变成蛇身，这个食物变成了蛇头），此时，用双端队列存储较好。

综上所述，可以判断蛇身用双端队列存储。

解决方案：

先读入地图，判断地图中有几条蛇，再读入每条蛇的移动操作。
第 i 条蛇的的身体用双端队列 q[i] 存储。其中，q[i].front() 表示蛇头的位置，q[i].back() 表示蛇尾的位置。

蛇的编号按题目要求计算（题目的输入格式中有描述）。

按照题意模拟蛇的移动，此代码使用的是双端队列与地图模拟相结合的方式，即：

双端队列存储蛇坐标，每次用队头（存的是蛇头的坐标）进行移动模拟。

地图模拟用来判断移动后蛇头是否会撞到另一条蛇，即蛇移动后是否会死亡；

按题意输出。

注意：

检查 freopen 是否注释。
检查移动函数中有没有重复判断情况，即一个 if 成立后另一个 if 也成立，这里推荐用 if-else 语句或 switch语句判断，防止重复。

代码：

一行代码的注释要么在这一行代码的后面，要么在下一行。若多行注释，则使用下面的格式：

/*
    ...
    ...
*/

建议最大化窗口观看。

无注释代码

#include<iostream>//cin+cout
#include<cstring> 
#include<cstdio> //freopen
#include<deque>  //双端队列的头文件 
#include<algorithm> //sort 
#define int long long 
using namespace std; 

int fx[1001],fy[1001];//向上下左右移动函数 
bool vis[1005][1005]; //记录一条蛇的身体是否被搜过（仅在 input() 函数中使用） 
char map[1005][1005]; //存储地图 
int c[1005][1005];    //存储 int 类型的操作 

struct P { int l,id; } ans[1<<17]; //记录移动操作后每条蛇的长度及编号 
bool cmp(P a,P b) { return a.l>b.l||(a.l==b.l&&a.id<b.id); }
//按题意，写出 sort 中的排序函数 cmp
//输出按长度由大到小排序（长度相同按编号由小到大排序） 

deque<pair<int,int> >a[25];
/*
    c<=20，双端队列开 20 个足够。 

    a[i] 存储一条蛇的坐标， 
    其中，
    a[i].front() 表示蛇头 
    a[i].back() 表示蛇尾 

    对于每一个 pair(x,y)
    first 表示横坐标 x
    second 表示纵坐标 y 
*/

int n,m,k,food,cnt;
/*
    地图 n 行 m 列 
    有 k 次操作
    地图中共有 food 个食物
    地图中共有 cnt 条蛇 
*/

//void output_map(); //输出地图（调试用） 

void input()
{
    fx[1]=0;fy[1]=-1;//向左 
    fx[2]=0;fy[2]=1; //向右 
    fx[3]=-1;fy[3]=0;//向上
    fx[4]=1;fy[4]=0; //向下 

    //为在输入地图后搜索蛇身，
    //初始化搜索函数 fx[1]~fx[4],fy[1]~fy[4] 

    fx['A']=0;fy['A']=-1;//向左 
    fx['D']=0;fy['D']=1; //向右 
    fx['W']=-1;fy['W']=0;//向上 
    fx['S']=1;fy['S']=0; //向下 

    //对于操作 'A','D','W','S',
    //初始化移动函数

    //两个初始化不会引起冲突：(int)'A'>4 

    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin>>map[i][j];
        food+=map[i][j]=='&'; //计算输入图中的食物数量 
        if(map[i][j]=='@') //如果发现一条蛇的蛇头 
        {
            cnt++; //蛇数量加一 
            a[cnt].push_back(make_pair(i,j)); //双端队列里加入蛇头坐标 (i,j)
            vis[i][j]=1;
        }
    }

//  output_map(); //输出地图（调试用） 

//  printf("\n------------------\n");

    char cc; //存储 char 类型的操作 
    for(int i=1;i<=cnt;i++)
    for(int j=1;j<=k;j++)
    cin>>cc,c[i][j]=cc; //cc 作为中介，把 char 类型的移动操作转换成 int 类型的移动操作  

    for(int i=1;i<=cnt;i++) //枚举每条蛇，存储每条蛇蛇身坐标
    {
        while(true) //广搜，用来搜索蛇身（深搜也可） 
        {   
            bool f=1; //标记此次扩展中队尾有没有加入新的节点
            int x=a[i].back().first,y=a[i].back().second;
            //a[i].back() 为当前蛇尾的坐标 (x,y)

            for(int k=1;k<=4;k++) //从当前节点向上下左右四个方向扩展 
            {
                int xx=x+fx[k],yy=y+fy[k]; //扩展节点的坐标 
                if(vis[xx][yy]) continue; //搜索过这个点，继续循环 
                if(map[xx][yy]=='#') //如果这个点是蛇身 
                a[i].push_back(make_pair(xx,yy)),f=0,vis[xx][yy]=1;
                /*
                    向队尾中加入当前新的蛇尾坐标 (xx,yy) 
                    f=0，记录队尾加入了新节点
                    vis[xx][yy]=1，标记点 (xx,yy) 已被搜索过 
                */
            }

            if(f) break;
            /*
                若 f=1，则此次扩展中队尾没有加入新的节点， 
                则这条蛇的身体已经被搜完了，就结束循环，去记录下一条蛇的坐标 
            */ 
        }
    }
}

void clear(int nw) //从队列和地图中清除编号为 nw 的蛇 
{
    while(a[nw].size()) //遍历这条蛇的节点 
    {
        int x=a[nw].front().first,y=a[nw].front().second;
        //从队首开始清除这条蛇，当前清除到的节点坐标为 (x,y)
        a[nw].pop_front(); //弹出队首坐标 
        map[x][y]='&'; //地图中这个节点变为食物 
        food++; //总食物 food 加一 
    }
}

void move(int nw,int t) //第 nw 条蛇的第 t 个操作 
{
    if(a[nw].empty()) return;
    //如果这条蛇的长度为 0，即这条蛇死亡，此次操作忽略 

    int x1=a[nw].front().first,x2=a[nw].back().first;
    int x=x1+fx[c[nw][t]];
    int y1=a[nw].front().second,y2=a[nw].back().second;
    int y=y1+fy[c[nw][t]];
    /*
        坐标 (x1,y1)：移动前蛇头坐标 
        坐标 (x2,y2)：移动前蛇尾坐标 
        坐标 (x,y)：移动后蛇头坐标 
    */ 

    //移动后的情况判断： 
    if(x<1||y<1||x>n||y>m) clear(nw);//蛇头超出边界，这条蛇死亡（详见题目基本规则中的第 5 条） 
    else if(map[x][y]=='#'||map[x][y]=='@') clear(nw);//蛇头撞上一头蛇，这条蛇死亡（详见题目基本规则中的第 4、6、7 条） 
    else if(map[x][y]=='&') a[nw].push_front(make_pair(x,y)),food--,map[x1][y1]='#',map[x][y]='@';
    /*
        移动后蛇吃到了一个食物：
            移动后食物变成了蛇头，移动前的蛇头变成了蛇身
            即在队首加入此食物的坐标，队尾不变，同时食物总数量 food 减一

        修改地图：
            坐标 (x1,y1)：为蛇身
            坐标 (x2,y2)：为蛇身
            坐标 (x,y)：为蛇头
        （详见题目基本规则中的第 2 条）
    */ 
    else if(map[x][y]=='.') a[nw].push_front(make_pair(x,y)),a[nw].pop_back(),map[x1][y1]='#',map[x][y]='@',map[x2][y2]='.';
    /*
        普通移动操作：
            在队首加入坐标 (x,y)，弹出队尾

        修改地图：
            坐标 (x1,y1)：为蛇身
            坐标 (x2,y2)：为空地
            坐标 (x,y)：为蛇头
        （详见题目基本规则中的第 1 条）
    */
}

/*

void output_map()  //输出地图（调试用） 
{
    for(int i=1;i<=n;i++ , puts(""))
    for(int j=1;j<=m;j++) putchar(map[i][j]);
    puts("--------------------\n\n");
}

*/

signed main()
{
//  freopen("a.in","r",stdin);

    input(); //输入，存储每一条蛇的坐标 

    for(int i=1;i<=k;i++) //k 次操作
    {
        for(int j=1;j<=cnt;j++) //cnt 条蛇 
        move(j,i); //第 j 条蛇的第 i 个操作 

//      output_map(); //输出地图（调试用） 
    }

    for(int i=1;i<=cnt;i++) //共有 cnt 条蛇 
    ans[i].l=a[i].size(),ans[i].id=i; //存储操作后每一套蛇的长度及编号 

    sort(ans+1,ans+1+cnt,cmp); //排序 

    for(int i=1;i<=cnt;i++) //共有 cnt 条蛇 
    cout<<ans[i].l<<" "<<ans[i].id<<endl; //输出排序后的蛇的长度和编号 

    cout<<food; //输出操作后的食物总个数 

    return 0;
}

P4944 PION贪吃蛇 题解

题目描述：

蛇身的存储：

解决方案：

注意：

代码：

P4944 PION贪吃蛇题解