题目相关:
3804相关链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5336
宠物(minion)在N*M的矩形玩游戏, 0表示睡眠(sleep), 1表示清醒(awake), 每一轮按照一定的规则进行状态变迁
具体的游戏规则如下:
1). 每个宠物在清醒状态(awake 1)时, 若太孤单(周边awake minion数<2), 太吵闹(周边awake minion数>3), 则转为睡眠状态(sleep 0)
2). 每个宠物在睡眠状态(sleep 0)时, 若周边awake minion数刚好为3时, 则该宠物进入清醒状态
3). 宠物会觉得这个游戏无聊, 在某一个时刻, 选择离开, 状态转为'X'
邻近关系以周边8个方向为依据.
思路解析:
本体为模拟题, 简单模拟即可. 唯一需要注意的是, 迭代的次数很多, 可以借助滚动数组的优化技巧来解决.
AC代码:
#include <cstdio>
#include <vector>
#include <algorithm>
struct move_t {
int t;
int x;
int y;
move_t(int t = 0, int x = 0, int y = 0)
: t(t), x(x), y(y) {
}
};
struct compare_func_t {
bool operator() (const move_t &lhs, const move_t &rhs) const {
return lhs.t < rhs.t;
}
};
// *) 用于统计周边字符为 ch 的个数
inline int sensor(char cmap[64][64], int n, int m, int y, int x, char ch) {
// *) 遍历八角的范围
static int DIRECIONS[8][2] = {
{1, 0}, {-1, 0}, {0, 1}, {0, -1},
{1, 1}, {-1, 1}, {1, -1}, {-1, -1}
};
int result = 0;
for ( int i = 0; i < 8; i++ ) {
int dx = x + DIRECIONS[i][0];
int dy = y + DIRECIONS[i][1];
if ( dx >= 0 && dx < m && dy >= 0 && dy < n ) {
if ( cmap[dy][dx] == ch ) {
result ++;
}
}
}
return result;
}
int main()
{
int kase;
int n, m, f, k;
char data[2][64][64];
scanf("%d", &kase);
while ( kase-- > 0 ) {
scanf("%d%d%d%d", &n, &m, &f, &k);
int before = 0, after = 1;
for ( int i = 0; i < n; i++ ) {
scanf("%s", data[before][i]);
}
int forward = 0;
std::vector<move_t> moves;
int t, x, y;
for ( int i = 0; i < k; i++ ) {
scanf("%d%d%d", &t, &y, &x);
moves.push_back(move_t(t, x, y));
}
std::sort(moves.begin(), moves.end(), compare_func_t());
for ( int i = 0; i < f; i++ ) {
// *) 一轮迭代, 进行状态变化
for ( int s = 0; s < n; s++ ) {
for ( int k = 0; k < m; k++ ) {
data[after][s][k] = data[before][s][k];
if ( data[before][s][k] == '0' ) {
int val = sensor(data[before], n, m, s, k, '1');
if ( val == 3 ) {
data[after][s][k] = '1';
}
} else if ( data[before][s][k] == '1' ) {
int val = sensor(data[before], n, m, s, k, '1');
if ( val < 2 || val > 3 ) {
data[after][s][k] = '0';
}
}
}
}
// *) 有人离开游戏
while ( forward < moves.size() ) {
const move_t &mv = moves[forward];
if ( mv.t <= i + 1 ) {
data[after][mv.y - 1][mv.x - 1] = 'X';
forward++;
} else {
break;
}
}
// *) 滚动数组进行切换
before ^= after ^= before ^= after;
}
// *) 输出结果
for ( int i = 0; i < n; i++ ) {
data[before][i][m] = '\0';
printf("%s\n", data[before][i]);
}
}
return 0;
}