TopCoder SRM 498 – DIV 1 Level 2

The solution of the problem is as follows.

#define MP     make_pair
typedef long long   LL;

int xx[]={-1,-1,0,1,1,1,0,-1};
int yy[]={0,-1,-1,-1,0,1,1,1};

vector<int> res;

void bfs(vector<vector<int> >&v, int n, int m, int x, int y){
    queue<pair<int, pair<int,int> > > q;
    q.push(MP(1, MP(x, y)));
    while(!q.empty()){
        int val = q.front().first;
        x = q.front().second.first;
        y = q.front().second.second;
        q.pop();
        if(x < 0 || y < 0) continue;
        if(x >= n || y >= m) continue;
        if(v[x][y]) continue;
        v[x][y] = val;
        res[val]++;
        for(int k=0; k<8;k++)
            q.push(MP(val+1, MP(x+xx[k], y+yy[k])));
    }
}

void bfs1(vector<vector<int> >&v, int n, int m, int x, int y){
    vector<vector<pair<int,pair<int,int> > > > mark(202);
    vector<vector<bool> > vis(n, vector<bool>(m, 0));
    queue<pair<int, pair<int,int> > > q;
    q.push(MP(1, MP(x, y)));
    while(!q.empty()){
        int val = q.front().first;
        x = q.front().second.first;
        y = q.front().second.second;
        q.pop();
        if(x < 0 || y < 0) continue;
        if(x >= n || y >= m) continue;
        if(vis[x][y]) continue;
        vis[x][y] = true;
        mark[val].PB(MP(v[x][y], MP(x,y)));
        for(int k=0; k<8 ;k++)
            q.push(MP(val+1, MP(x+xx[k], y+yy[k])));
    }
    int it = 1;
    for(int i=1; i<202 ;i++){
        map<int,int> mapa;
        for(int j=0; j<mark[i].size();j++){
            int val = mark[i][j].first;
            x = mark[i][j].second.first;
            y = mark[i][j].second.second;
            if(mapa.find(val) == mapa.end()) mapa[val] = it++;
            v[x][y] = mapa[val];
        }
    }
}

LL fact(int x){
    LL r=1;
    for(LL i=2; i<=LL(x) ;i++)
        r = (r*i)%1000000009LL;
    return r;
}

class FoxStones{
    public:
    int getCount(int n, int m, vector<int> sx, vector<int> sy) {
        vector<vector<int> > v(n, vector<int>(m, 0));
        res = vector<int> (201, 0);
        bfs(v, n, m, sx[0]-1, sy[0]-1);
        for(int i=1; i            bfs1(v, n, m, sx[i]-1, sy[i]-1);
        vector<int> sol(40002, 0);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                sol[v[i][j]]++;
        LL r = 1LL;
        for(int i=0;i<sol.size();i++)
            if(sol[i])
                r = (r*fact(sol[i]))%1000000009LL;
        return r;
    }
};