P4944 题解
liangbowen
2022-06-05 08:47:30
### 前言
[题目传送门！](https://www.luogu.com.cn/problem/P4944)
[或许更好的阅读体验？](https://www.luogu.com.cn/blog/liangbowen/solution-P4944)
这题算是一道中模拟？
码量不会很高，大概只有 $100$ 至 $150$ 行。
### 思路
1. 输入地图。
注意，还不能读入蛇的行动指令，因为我们不知道**有几条蛇**。
2. 使用广搜得出每条蛇的信息。
这个就是**搜连通块**，惟一不同的是，要使用队列存下这条蛇。
3. 写一个死亡函数，处理蛇死亡后的信息。
这个并不困难，只要将队列清空，顺便将整条蛇蛇**变成食物**。
4. 写移动函数，这里要分几种情况考虑。
+ 移动后撞上墙，死掉。
+ 移动后撞上身体（当然也包括头），死掉。
此处的『撞上身体』既包括别人的身体，也包括自己的身体。
+ 移动后有食物。
我们可以让其他部位保持不动，蛇头向食物处扩充一格。
+ 移动后，什么都没有，是平地。
我们可以做两件事达到效果：
首先扩充蛇头。
然后消除蛇尾。
用普通的队列难以达到这种效果，因此可以使用**双端队列**。
5. 读入蛇的行动指令，并移动。
6. 最后输出。
由于题目让我们**按顺序输出**，所以我们需要排序。
然后还要再扫一遍地图，记录食物数量。
### 坑点
这些坑点指，题目并没有说清楚的地方，更多细节请查看代码。
1. 很多人都有疑问，为什么可以直接**搜连通块**分辨每条蛇。
很多人都忽略了一个细节，题目保证了：
> 图中的蛇不会引起混淆（对于任意蛇头，最多只有一块蛇身于其相连，而**蛇身最多为二连块**）。
因此，直接搜连通块是可行的。
2. 蛇的移动顺序。
蛇是按照**回合制**移动的，每一回合，编号小的蛇优先行动。
### 完整代码
```cpp
#include <iostream>
#include <cstdio>
#include <queue> //包含 queue 与 deque 两种数据类型。
#include <algorithm> //用于 sort 排序。
#define N 205
#define C 25
using namespace std;
int n, m, k;
int cur; //表示蛇的数量。
char a[N][N]; //表示地图。
int who[N][N]; //表示当前格子属于那一条蛇。
//后来发现这个 who 数组完全没使用到，所以不写也行。
string order[C]; //代表蛇的行动指令。
struct node
{
int x, y;
};
deque <node> snake[C]; //模拟当前的蛇。
void Input1(); //输入地图，不解释。
void bfs(); //搜索得出蛇的位置。
void debug(); //调试工具。
void die(int id); //第 id 条蛇死亡了。
void move(int id, char op); //对第 id 条蛇执行 op 指令。
void Input2(); //输入蛇的运行指令，但顺便利用 move() 函数移动处理。
void Output(); //输出答案。
int main()
{
Input1();
bfs();
//debug();
Input2();
//debug();
Output();
return 0;
}
void Input1() //实际输入只能输入一部分，因为必须 bfs 得出蛇的数量后，再输入指令。
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
}
int dict[5][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void bfs() //爆搜，没什么技巧。
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i][j] == '@')
{
cur++;
queue <node> Q;
Q.push( (node){i, j} );
while (!Q.empty())
{
int x = Q.front().x, y = Q.front().y;
who[x][y] = cur;
snake[cur].push_back( (node){x, y} );
Q.pop();
for (int i = 0; i <= 3; i++)
{
int dx = x + dict[i][0], dy = y + dict[i][1];
if (dx < 1 || dx > n || dy < 1 || dy > m) continue;
if (who[dx][dy] == cur) continue;
if (a[dx][dy] == '#') Q.push( (node){dx, dy} );
}
}
}
}
void debug()
{
for (int i = 1; i <= cur; i++)
{
printf("\ni = %d:\n", i);
deque <node> Q = snake[i];
while (!Q.empty())
{
printf("(%d %d) ", Q.front().x, Q.front().y);
Q.pop_front();
}
}
}
void die(int id)
{
while (!snake[id].empty())
{
int x = snake[id].front().x, y = snake[id].front().y;
who[x][y] = 0; //消除标记。
a[x][y] = '&'; //变成食物。
snake[id].pop_front(); //把蛇给消除。
}
}
void move(int id, char op)
{
int x = snake[id].front().x, y = snake[id].front().y;
if (op == 'W') x--; //往上。
if (op == 'S') x++; //往下。
if (op == 'A') y--; //往左。
if (op == 'D') y++; //往右。
if (x < 1 || x > n || y < 1 || y > m) //撞边界上了，死亡。
{
die(id);
return;
}
if (a[x][y] == '#' || a[x][y] == '@') //撞身体上了，死亡。
{
die(id);
return;
}
int head_x = snake[id].front().x, head_y = snake[id].front().y; //原先的蛇头。
int tail_x = snake[id].back().x, tail_y = snake[id].back().y; //原先的蛇尾。
if (a[x][y] == '&') //吃到食物，直接扩充蛇。
{
snake[id].push_front( (node){x, y} );
a[x][y] = '@'; //食物处变成蛇头。
a[head_x][head_y] = '#'; //曾经的蛇头变成蛇身。
who[x][y] = id; //标记蛇。
}
if (a[x][y] == '.') //是平路，蛇头扩充，蛇尾消除。
{
//蛇头扩充。
snake[id].push_front( (node){x, y} );
a[x][y] = '@';
a[head_x][head_y] = '#';
who[x][y] = id;
//蛇尾消除。
snake[id].pop_back();
a[tail_x][tail_y] = '.';
who[tail_x][tail_y] = 0;
}
}
void Input2()
{
for (int i = 1; i <= cur; i++) cin >> order[i];
for (int j = 0; j < k; j++)
for (int i = 1; i <= cur; i++)
if (!snake[i].empty()) //需要注意，只有蛇没有死亡，才可以移动。
move(i, order[i][j]);
}
struct Snake
//存储每条蛇的信息。
{
int len, id;
}p[C];
bool cmp(Snake x, Snake y)
{
if (x.len != y.len) return x.len > y.len;
return x.id < y.id;
}
void Output()
{
//计算每条蛇的信息。
for (int i = 1; i <= cur; i++)
{
p[i].id = i;
deque <node> Q = snake[i];
while (!Q.empty())
{
p[i].len++;
Q.pop_back();
}
}
sort(p+1, p+cur+1, cmp); //按题目所述排序。
for (int i = 1; i <= cur; i++) printf("%d %d\n", p[i].len, p[i].id);
//计算食物数量并输出。
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i][j] == '&')
cnt++;
printf("%d", cnt);
}
```