HackerRank The Bomberman Game(Algorithms>Implementation)

題目:
炸彈超人存在在一個矩形的區塊，
這個區塊有R行C列(R rows and C columns)。
每一個區塊內的方格(cell)要嘛有一個炸彈，
要嘛就是空的。

每個炸彈可以被放在區塊內的任意方格中，
一旦放置，在倒數3秒後會爆炸，
並且摧毀連同周邊的四個方格。
也就是說在i, j座標的方格裡的炸彈引爆，
會讓(i+-1, j)和(i, j+-1)的方格被清空。
(注意在邊緣的格子可能周邊少於4個方格)
如果周邊的格子在被清空時有炸彈的話，
該炸彈會被摧毀，但不會再被引爆。
(也就是不會有連鎖反應)

炸彈超人對炸彈是免疫的(最好啦!怎麼跟我小時候玩的不一樣)，
所以他可以在區塊內任意移動。
下面是他所做的:
1. 最初炸彈超人任意在區塊內的一些格子放置炸彈。
2. 1秒後，炸彈超人不做任何事情。
3. 再多1秒後，炸彈超人將剩下沒被放炸彈的格子放滿炸彈，
也就是保證現在所有格子都有炸彈，且這一秒還沒有炸彈會爆炸。
4. 再多1秒後，3秒前被放的炸彈會爆炸，這裡，炸彈超人退後並觀測。
5. 然後炸彈超人不停反覆進行步驟3和步驟4。

注意每次炸彈超人放的炸彈都視為同時放，
所以同時放的炸彈也會同時爆炸(一個光速的概念就對了)

給定初始放炸彈的格子，
決定N秒後區塊的狀態。

輸入:
第一行包含了3個用空格隔開的整數，
分別代表R,C,N，
R條連續的線(line)i代表行(row)i在區塊內的起始狀態，
以'.'表示空方格，O(ascii 79)表示炸彈。

限制:
1<=R, C<=200
1<=N<=10的9次方

輸出:
印出區塊的最終狀態，
也就是要印出R行C列的字母，
當中每個字母會是'.'(沒炸彈)或'O'(有炸彈)，
用以表示N秒後的區塊狀態。

範例輸入:

6 7 3
.......
...O...
....O..
.......
OO.....
OO.....

範例輸出:

OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO

解題:
這題有相當程度的麻煩，在實作時也要考慮到一些東西。
首先考慮如何計算狀態變化，
我們以B1表示最初放的炸彈，
B2表示2秒後填滿的那次，
以此類推，那麼我們大概可以藉由下面列出的時間軸看出一些端倪。
0----->1----->2----->3--------->4------->5----------->6------>7
B1      X        B2      X(B1炸)   B3        X(B2炸)     B4       X(B3炸)

t=0時，放下B1
t=1時，不變(也就是說N=1的話就可以直接按照原輸入的陣列輸出。)
t=2時，放下B2(這時候填滿了)
t=3時，B1炸開來
t=4時，放下B3(這時候又填滿了)
......
所以，我們可以知道:
1. N=1 => 直接輸出原陣列
2. N%2 = 0 => 輸出全填滿'O'(因為這時候炸彈全填滿)
3. 其他
考慮B1炸開來的時候，炸開的範圍是B1加上其前後左右。
(注意不會連鎖引爆，會的話又不一樣了)
由於這時候t=3，我們先叫它t3 state。

t3 state在t=4的時候補下B3，跟著t=5時又爆炸，
炸開的範圍是t3加上其前後左右，
會留下除了(t3及其前後左右)以外的格子，
我們叫它t5 state。

t5到t7又炸一次，不難得知t7=t3 state(因為剛好互補)。
所以可知t3=t7=t11=...=t(4r+3), r = 0,1,2, ...
同樣的，t5=t9=t13=...=t(4k+1), k= 0,1,2, ...

所以t1到t3作的事情，
就是先expand(延展)以後，再reverse(取互補)。
t3到t5只是做同樣的事情一次，
但t1不等同於t5就是了。

下面在宣告時，由於二階陣列不宜動態宣告(記憶體配置容易管理不好)，
我們可以藉由限定的行列數在200以下，直接宣告grid[201][201]。
(剛好200會出錯，不清楚為什麼，如果有看出我寫法問題的還請不吝賜教，感謝~)

讀入時記得先讀入R,C,N，
然後每一行由於是讀字元，不要忘記多讀一次將LF換行字元讀走。
剩下的重點就是expAndRev的部分了:
首先傳入二維以上的陣列時，第二個維度以後要先給值，
故使用的是grid[][201]傳入。
再來，在expand的部分，
要注意的是先檢查該格是否是炸彈('O')，
再作延展的動作，而且不能同樣標記為'O'，
否則在另一輪迴圈裡可能會當作是新的炸彈，
這樣就變成連鎖反應了。
這邊用'E'來表示延展的格子。

最後reverse時，檢查是否為有炸彈或被延展(!= '.' )，
有的話就回歸為空格，不然就反轉為炸彈格('O')。

其他要留意的部分，
如expand時兩個if是不能寫到一起的，
因為有可能發生超過界線的狀態。


Code：

/* 
 Solve by Desolve Lin, 2016/09/15
 Please help yourself take it for reference,
 but kindly have a link to my blog if you use it at other website,
 thanks a lot!
*/

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void printAns(int r, int c, char grid[][201]){
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            printf("%c", grid[i][j]);
        }
        printf("\n");
    }
}

void printFull(int row, int column){
    for(int i = 0; i < row; i++){
        for(int j = 0; j < column; j++){
                printf("O");
        }
        printf("\n");
    }
}

// t3 result
void expAndRev(int row, int column, char grid[][201]){
    // Expand to find detonate area
    for(int i = 0; i < row; i++){
        for(int j = 0; j < column; j++){
            if(grid[i][j] == 'O'){
                // Those who are detonated areas are not real bomb and can't be expanded again.
                if(i - 1 >= 0)
                    if(grid[i-1][j] == '.')
                        grid[i-1][j] = 'E';
                if(j - 1 >= 0)
                    if(grid[i][j-1] == '.')
                        grid[i][j-1] = 'E';
                if(i + 1 < row) 
                    if(grid[i+1][j] == '.')
                        grid[i+1][j] = 'E';
                if(j + 1 < column) 
                    if(grid[i][j+1] == '.')
                        grid[i][j+1] = 'E';
            }
        }
    }
    // Reverse to find t3 bomb state        
    for(int i = 0; i < row; i++){
        for(int j = 0; j < column; j++){
            if(grid[i][j] != '.'){
                grid[i][j] = '.';
            }else{
                grid[i][j] = 'O';
            }    
        }
    }   
}

int main() {
    int row, column, n;
    scanf("%d %d %d\n", &row, &column, &n);
    char grid[201][201];
    
    for(int i = 0; i < row; i++){
        char tmp;
        for(int j = 0; j < column; j++){            
            scanf("%c", &grid[i][j]);
        }
        scanf("%c", &tmp); // remove linefeed
    }
    if(n == 1)
        printAns(row, column, grid);
    else if(n % 2 == 0)
        printFull(row, column);
    else{
        // t3 state => expand and reverse once : t3, 7, 11, 15
        // t5 state => expand and reverse twice: t5, 9, 13, 17
        expAndRev(row, column, grid);
        if(n % 4 == 1)
            expAndRev(row, column, grid);
        printAns(row, column, grid);
    }    
    return 0;
}