The Bomberman Game [HackerRank : HourRank 10]

問題

https://www.hackerrank.com/contests/hourrank-10/challenges/bomber-man

縦R横Cのマスがある。
最初に幾つかの爆弾が設置されている(これが1秒目)。
以下のように、毎秒ごとに状態が遷移するものとして、N秒後はどのような盤面になっているか？

1. 爆弾が設置されていない部分に爆弾を設置する
2. 1.で設置した爆弾以外の爆弾が爆発し、縦横を含む5マスにある爆弾が爆発せずに消える
3. 1.と2.を無限に繰り返す

1 <= R,C <= 200
1 <= N <= 10^9

考察

1. まずは、Sample Inputで実験してみる

.......    OOOOOOO    OOO.OOO    OOOOOOO    .......
...O...    OOOOOOO    OO...OO    OOOOOOO    ...O...
....O..    OOOOOOO    OOO...O    OOOOOOO    ....O..
....... -> OOOOOOO -> ..OO.OO -> OOOOOOO -> ....... -> ...
OO.....    OOOOOOO    ...OOOO    OOOOOOO    OO.....
OO.....    OOOOOOO    ...OOOO    OOOOOOO    OO.....
 1秒目      2秒目      3秒目      4秒目      5秒目

2. これを見て分かるのが、偶数目はとりあえず全部爆弾
3. 周期性がありそう？(N=10^9なので周期性を使ったものな感じがある)
4. i秒目のとき、i%4==1のときとi%4==3のときで場合分けして答えればいいんじゃない？？

• > これで提出 -> WA

5. なんでや
6. こんな感じのサンプルもう一個欲しかった

.O..    OOOO    ...O    OOOO    OO..    OOOO    ...O
O.O. -> OOOO -> .... -> OOOO -> O.O. -> OOOO -> .... -> ...
....    OOOO    .O.O    OOOO    ....    OOOO    .O.O

7. i%4==1は最初だけ違ってそれ以降は一緒となるみたいなので、それだけ注意する

実装

https://www.hackerrank.com/contests/hourrank-10/challenges/bomber-man/submissions/code/6254553

int R, C, N;
vector<string> B;
//-----------------------------------------------------------------
vector<string> allO() {
	return vector<string>(R, string(C, 'O'));
}
//-----------------------------------------------------------------
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
vector<string> denonate(vector<string> vs) {
	vector<string> ret = allO();

	rep(i, 0, R) rep(j, 0, C) if (vs[i][j] == 'O') {
		ret[i][j] = '.';
		rep(k, 0, 4) {
			int ii = i + dx[k];
			int jj = j + dy[k];
			if (ii < 0 || R <= ii) continue;
			if (jj < 0 || C <= jj) continue;
			ret[ii][jj] = '.';
		}
	}

	return ret;
}
//-----------------------------------------------------------------
int main() {
	scanf("%d %d %d", &R, &C, &N);

	rep(i, 0, R) {
		string s; cin >> s;
		B.push_back(s);
	}

	if (N % 2 == 0) {
		vector<string> vs = allO();
		rep(i, 0, R) printf("%s\n", vs[i].c_str());
		return 0;
	}

	if (N == 1) {
		rep(i, 0, R) printf("%s\n", B[i].c_str());
		return 0;
	}

	vector<string> B1 = denonate(B);
	vector<string> B2 = denonate(B1);

	N %= 4;

	if (N == 1) {
		rep(i, 0, R) printf("%s\n", B2[i].c_str());
	}
	else {
		rep(i, 0, R) printf("%s\n", B1[i].c_str());
	}
}