srm472 div2 - 1000

#include <iostream>
#include <queue>
#include <set>
using namespace std;


class RectangularIsland {

    static const int N = 4, dx[N], dy[N];
    long long** table, out, fav;
    int steps, width, height;
    queue<pair<int, int> > cells;

    void back()
    {
        set<pair<int, int> > toAdd;
        while (steps-- > 0) { // for each step
            for (set<pair<int, int> >::iterator it = toAdd.begin(); it != toAdd.end(); ++it) {
                cells.push(*it); // update queue
            }
            toAdd.clear();
            while (!cells.empty()) { // retrieve all positions in this state
                pair<int, int> cell = cells.front();
                cells.pop();
                for (int i = 0; i < N; ++i) {
                    long long& tmp = table[cell.first + dx[i]][cell.second + dy[i]];
                    if (tmp == -1) {
                        out += table[cell.first][cell.second];
                    } else {
                        tmp += table[cell.first][cell.second]; // update number of steps
                        toAdd.insert(make_pair(cell.first + dx[i], cell.second + dy[i]));
                    }
                }
                table[cell.first][cell.second] = 0;
            }
        }
    }

    void print_table()
    {
        for (int i = 0; i <= height + 1; ++i) {
            for (int j = 0; j <= width + 1; ++j) {
                cout << table[i][j] << " ";
            }
            cout << endl;
        }
    }

    public:
    double theProbablity(int width, int height, int y, int x, int steps)
    {
        this->width = width;
        this->height = height;
        this->steps = steps;
        out = fav = 0;
        table = new (nothrow) long long*[height + 2];
        int i, j; // memory allocation
        for (i = 0; i <= height + 1; ++i) table[i] = new (nothrow) long long[width + 2];
        for (i = 0; i <= width + 1; ++i) {
            table[0][i] = -1;
            table[height + 1][i] = -1;
        } // create the margin [/\]_[\/]
        for (i = 0; i <= height + 1; ++i) {
            table[i][0] = -1;
            table[i][width + 1] = -1;
        }
        for (i = 1; i <= height; ++i) {
            for (j = 1; j <= width; ++j) {
                table[i][j] = 0; // fill the rest
            }
        }
        x = height - x;
        y = y + 1; // mark the start cell
        table[x][y] = 1;
        cells.push(make_pair(x, y));
        back();
        //print_table();
        for (i = 1; i <= height; ++i) {
            for (j = 1; j <= width; ++j) {
                fav += table[i][j]; // fill the rest
            }
        }
        //cout << fav << " " << out;
        return (double)fav / (fav + out);
    }
};

const int RectangularIsland::dx[] = {0, 0, -1, 1};
const int RectangularIsland::dy[] = {1, -1, 0, 0};