题意
给出一个地图,地图上初始有
接下来会给出
分析&代码
写一个 Snake
类,来存放所有有关蛇的操作。
struct node { //结点 int x, y; }; class Snake { private: std::deque body; //蛇 void die(void) { //清除蛇身 live = false; len = 0; while (!body.empty()) { node cac = body.front(); body.pop_front(); map[cac.x][cac.y] = '&', restFood++; } return; } public: Snake(int x, int y, int id) { //BFS 寻找蛇身 this->id = id; len = 0; live = true; static std::queue que; que.push((node){x, y}); while (!que.empty()) { node cac = que.front(); vis[cac.x][cac.y] = true; body.push_back(cac), len++; que.pop(); for (int i = 0; i < 4; i++) { int tx = cac.x + way[0][i], ty = cac.y + way[1][i]; if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && !vis[tx][ty] && map[tx][ty] == '#') que.push((node){tx, ty}); } } return; } ~Snake(void) { body.clear(); return; } bool live; int id, len; void move(char way) { node to = body.front(); map[to.x][to.y] = '#'; //删除蛇头 if (way == 'W') to.x--; //四个方向 if (way == 'S') to.x++; if (way == 'A') to.y--; if (way == 'D') to.y++; if (to.x < 1 || to.x > n || to.y < 1 || to.y > m || map[to.x][to.y] == '#' || map[to.x][to.y] == '@') return die(); //如果撞到蛇身或者边界 body.push_front(to), len++; if (map[to.x][to.y] == '&') return restFood--, void(map[to.x][to.y] = '@'); //吃食物 map[to.x][to.y] = '@'; map[body.back().x][body.back().y] = '.'; //删除尾部,增加新的头部 return len--, body.pop_back(); } inline bool operator<(const Snake& oth) const { return this->len > oth.len || this->len == oth.len && this->id < oth.id; } };
其中构造函数负责 BFS 初始化蛇身,move(char)
函数负责让蛇向指定方向移动。此时如果蛇死了会直接调用 die(void)
清除蛇身。
这里有一点巧的就是在蛇吃掉食物后,只要让食物变成新蛇头就可以了。
如果蛇没有吃掉食物,删除蛇尾并且在前方标记新头即可。
上面的类定义完之后,面向对象模拟题意即可。
int main() { std::ios::sync_with_stdio(false); int k, c; std::cin >> n >> m >> k; restFood = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { std::cin >> map[i][j]; if (map[i][j] == '&') restFood++; } c = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (map[i][j] == '@') snakes.push_back((Snake){i, j, ++c}); //通过蛇头直接初始化蛇身 for (int i = 0; i < c; i++) for (int j = 1; j <= k; j++) std::cin >> cmd[i][j]; for (int tim = 1; tim <= k; tim++) for (int p = 0; p < c; p++) { if (!snakes[p].live) continue; snakes[p].move(cmd[p][tim]); //让蛇向指定方向移动一格 } std::sort(snakes.begin(), snakes.end()); for (std::vector::iterator i = snakes.begin(); i != snakes.end(); i++) std::cout << i->len << ' ' << i->id << std::endl; std::cout << restFood << std::endl; return 0; }
完整代码:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <cstdio> | |
#include <iostream> | |
#include <queue> | |
#include <vector> | |
const int maxn = 205; | |
const int maxk = 105; | |
const int way[2][4] = {{1, 0, -1, 0}, {0, 1, 0, -1}}; | |
char map[maxn][maxn], cmd[maxn][maxk]; | |
bool vis[maxn][maxn]; | |
int n, m, restFood; | |
struct node { | |
int x, y; | |
}; | |
class Snake { | |
private: | |
std::deque<node> body; | |
void die(void) { | |
live = false; | |
len = 0; | |
while (!body.empty()) { | |
node cac = body.front(); | |
body.pop_front(); | |
map[cac.x][cac.y] = '&', restFood++; | |
} | |
return; | |
} | |
public: | |
Snake(int x, int y, int id) { | |
this->id = id; | |
len = 0; | |
live = true; | |
static std::queue<node> que; | |
que.push((node){x, y}); | |
while (!que.empty()) { | |
node cac = que.front(); | |
vis[cac.x][cac.y] = true; | |
body.push_back(cac), len++; | |
que.pop(); | |
for (int i = 0; i < 4; i++) { | |
int tx = cac.x + way[0][i], ty = cac.y + way[1][i]; | |
if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && | |
!vis[tx][ty] && map[tx][ty] == '#') que.push((node){tx, ty}); | |
} | |
} | |
return; | |
} | |
~Snake(void) { | |
body.clear(); | |
return; | |
} | |
bool live; | |
int id, len; | |
void move(char way) { | |
node to = body.front(); | |
map[to.x][to.y] = '#'; | |
if (way == 'W') to.x--; | |
if (way == 'S') to.x++; | |
if (way == 'A') to.y--; | |
if (way == 'D') to.y++; | |
if (to.x < 1 || to.x > n || to.y < 1 || to.y > m || | |
map[to.x][to.y] == '#' || map[to.x][to.y] == '@') return die(); | |
body.push_front(to), len++; | |
if (map[to.x][to.y] == '&') return restFood--, void(map[to.x][to.y] = '@'); | |
map[to.x][to.y] = '@'; | |
map[body.back().x][body.back().y] = '.'; | |
return len--, body.pop_back(); | |
} | |
inline bool operator<(const Snake& oth) const { | |
return this->len > oth.len || this->len == oth.len && this->id < oth.id; | |
} | |
}; | |
std::vector<Snake> snakes; | |
int main() { | |
std::ios::sync_with_stdio(false); | |
int k, c; | |
std::cin >> n >> m >> k; | |
restFood = 0; | |
for (int i = 1; i <= n; i++) | |
for (int j = 1; j <= m; j++) { | |
std::cin >> map[i][j]; | |
if (map[i][j] == '&') restFood++; | |
} | |
c = 0; | |
for (int i = 1; i <= n; i++) | |
for (int j = 1; j <= m; j++) | |
if (map[i][j] == '@') snakes.push_back((Snake){i, j, ++c}); | |
for (int i = 0; i < c; i++) | |
for (int j = 1; j <= k; j++) | |
std::cin >> cmd[i][j]; | |
for (int tim = 1; tim <= k; tim++) | |
for (int p = 0; p < c; p++) { | |
if (!snakes[p].live) continue; | |
snakes[p].move(cmd[p][tim]); | |
} | |
std::sort(snakes.begin(), snakes.end()); | |
for (std::vector<Snake>::iterator i = snakes.begin(); i != snakes.end(); i++) | |
std::cout << i->len << ' ' << i->id << std::endl; | |
std::cout << restFood << std::endl; | |
return 0; | |
} |
Comments | NOTHING