Topcoder SRM 590 DIV2 MEDIUM

graph problem, BFS need to be modified that it should keep records of current tokens'
border points, for maximum score, we only need to check tokens whose border number is
0 and 1, for 0, just add all tokens, for 1, do a n**2 iteration and add those pairs whose
border number equals 1 and the border point is the same

/* Topcoder SRM */
/*****************************************************************************/
struct point {
    int x, y;
    inline bool operator==(const point &o) const {
        return x==o.x&&y==o.y;
    }
};
struct token {
    int n;
    vector<point> p;
    inline bool operator==(const token &o) const {
        return sz(p)==1&&sz(o.p)==1&&p[0]==o.p[0];
    }
};
int n;
int d[4][2]={{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int v[20][20];
int vb[20][20];
vector<token> t;
void bfs(vector<string> &board, int i, int j) {
    token tk;
    tk.n=1;
    point s={i, j};
    queue<point> q;
    q.push(s);
    v[i][j]=1;
    while (!q.empty()) {
        point c=q.front(); q.pop();
        for (int i=0; i<4; i++) {
            int nx=c.x+d[i][0], ny=c.y+d[i][1];
            if (nx<0||nx>=n||ny<0||ny>=n) {
                continue;
            }
            if (v[nx][ny]||board[nx][ny]=='x') { continue; }
            if (vb[nx][ny]) {
                continue;
            }
            if (board[nx][ny]=='.') {
                point adj={nx, ny};
                tk.p.pb(adj);
                vb[nx][ny]=1;
                continue;
            }
            tk.n++;
            v[nx][ny]=1;
            point nc={nx, ny};
            q.push(nc);
        }
    }
    t.pb(tk);
}
int FoxAndGo::maxKill(vector <string> board) {
    n=sz(board);
    t.clear();
    memset(v, 0, sizeof(v));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (v[i][j]||board[i][j]!='o') {
                continue;
            }
            memset(vb, 0, sizeof(vb));
            bfs(board, i, j);
        }
    }
    int r=0;
    for (int i=0; i<sz(t); i++) {
        if (sz(t[i].p)==0) {
            r+=t[i].n;
        }
    }
    int rr=0;
    for (int i=0; i<sz(t); i++) {
        if (sz(t[i].p)!=1) {
            continue;
        }
        int cr=t[i].n;
        for (int j=i+1; j<sz(t); j++) {
            if (t[i]==t[j]) {
                cr+=t[j].n;
            }
        }
        rr=max(rr, cr);
    }
    return r+rr;
}
/*****************************************************************************/