首页 > 代码库 > ZOJ 3804--解题报告
ZOJ 3804--解题报告
题目相关:
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;}
ZOJ 3804--解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。