void explode(vector<string>* grid, vector<string>* result){
    for(int row = 0; row<(*grid).size(); row++){
        for(int col = 0; col<(*grid)[0].size(); col++){
            if((*grid)[row][col] == 'O') {
                (*result)[row][col] = '.';
                if (col-1>=0) (*result)[row][col-1] = '.';
                if (row-1>=0) (*result)[row-1][col] = '.';
                if (col+1<(*result)[0].size()) (*result)[row][col+1] = '.';
                if (row+1<(*result).size()) (*result)[row+1][col] = '.';
            }
        }
     }
}

vector<string> bomberMan(int n, vector<string> grid) {
    //These solutions are trivial
    if(n==1) return grid;
    string row(grid[0].size(), 'O');
    vector<string> result(grid.size(), row);
    if(n%2==0)return result;
    /*The first detonation and second detonation patterns keep repeating.
    The only thing I need to check is if n belongs to the arithmetic 
    sequence with d=4 and a1=3 (first detonation) or a1=5 (second detonation).*/
    explode(&grid, &result);
    if((n-3)%4==0) return result;
    grid = result;
    fill(result.begin(), result.end(), row);
    if((n-5)%4==0){
        explode(&grid, &result);
        return result;
    }
    return {"*"};
}