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] = '';
			printf("%s
", data[before][i]);
		}
	
	}	
	return 0;
}