SRM495 Div2 Hard(1000) HexagonPuzzle

TopCoder

HexagonPuzzle

トークンを移動可能なマスごとにグループに分ける。あるグループのマス数をcとするとc!の配置が考えられる。実際に可能な配置はc!/2。最後の２枚を除いては好きな位置に配置できるが、最後の２枚の位置を入れ替えることはできない。

#include <string>
#include <vector>
using namespace std;

//  Union-Find木
class UnionFind
{
    vector<int>p,r,c;
public:
    UnionFind(int n):p(n,-1),r(n),c(n,1){}
    int find(int x){return p[x]>=0?p[x]=find(p[x]):x;}
    void unite(int x,int y){x=find(x),y=find(y);
        if(x!=y)if(r[x]<r[y])p[x]=y,c[y]+=c[x];else p[y]=x,c[x]+=c[y],r[x]+=r[x]==r[y];}
    bool same(int x, int y){return find(x)==find(y);}
    int count(int x){return p[x]<0?c[x]:0;}
};

class HexagonPuzzle{public:
int theCount( vector <string> board )
{
    int M = 1000000007;
    int N = (int)board.size();

    UnionFind u(N*N);

    for ( int y=0; y<N-1; y++ )
    for ( int x=0; x<=y; x++ )
        if ( board[y  ][x  ]=='.'  &&
             board[y+1][x  ]=='.'  &&
             board[y+1][x+1]=='.' )
            u.unite(y*N+x,(y+1)*N+x  ),
            u.unite(y*N+x,(y+1)*N+x+1);

    for ( int y=1; y<N-1; y++ )
    for ( int x=0; x<y; x++ )
        if ( board[y  ][x  ]=='.'  &&
             board[y  ][x+1]=='.'  &&
             board[y+1][x+1]=='.' )
            u.unite(y*N+x, y   *N+x+1),
            u.unite(y*N+x,(y+1)*N+x+1);

    long long ans = 1;
    for ( int y=0; y<N; y++ )
    for ( int x=0; x<=y; x++ )
    {
        int c = u.count(y*N+x);
        for ( int i=3; i<=c; i++ )
            ans = ans*i%M;
    }

    return (int)ans;
}};