SRM 651 div2 hard:FoxConnection4

同じ回のdiv1medと同じ発想だったので早く解けてよかったのだが、mod 1000000009に惑わされて結構時間がかかった。

問題:一部のセルが埋められたH*Wの２次元グリッドが与えられる。空白セルのうちK個を選択したとき、それらが隣接セル同士で連結しているようなものは何通りあるか。
解法:div1 medと同様、セル同士が連結した形を全列挙して、そのそれぞれについて、各座標をスタートにしてセルを埋めることができるか調べる。
以下ソースコード

typedef long long ll;
typedef pair<int, int> P;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const ll INF = 1ll<<60;
const ll MOD = 1000000009;
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

vector<vector<P> > shape;
set<vector<P> > S;

bool seen(const vector<P>& vs) {
    int xmin = 10, ymin = 10;
    int n = vs.size();
    for (int i = 0; i < n; i++) {
        xmin = min(xmin, vs[i].first);
        ymin = min(ymin, vs[i].second);
    }
    vector<P> nvs;
    for (int i = 0; i < n; i++) {
        nvs.push_back(P(vs[i].first-xmin, vs[i].second-ymin));
    }
    sort(nvs.begin(), nvs.end());
    if (S.find(nvs) != S.end()) return true;
    else {
        S.insert(nvs);
        return false;
    }
}

void createShape(int n, int cur, vector<P>& path) {
    if (cur == n) {
        seen(path);
        return;
    }
    if (seen(path)) return;
    int m = path.size();
    for (int i = 0; i < m; i++) {
        P now = path[i];
        for (int k = 0; k < 4; k++) {
            P next = P(now.first+dx[k], now.second+dy[k]);
            if (find(path.begin(), path.end(), next) != path.end()) continue;
            path.push_back(next);
            createShape(n, cur+1, path);
            path.pop_back();
        }
    }
}

void print(vector<P> s) {
    for (int i = 0; i < (int)s.size(); i++) {
        cout << s[i].first << "   " << s[i].second <<endl;
    }
    cout << endl;
}

ll howMany(const vector<string>& board) {
    int h = board.size(), w = board[0].size();
    ll ret = 0;
    for (auto s : shape) {
        int k = s.size();
        //print(s);
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                int j = 0;
                for (; j < k; j++) {
                    if (s[j].first+x < 0 || s[j].first+x >= w || s[j].second+y < 0 || s[j].second+y >= h) break;
                    if (board[s[j].second+y][s[j].first+x] == '#') break;
                }
                if (j == k) ret++;
            }
        }
    }
    return ret;
}

class FoxConnection4 {
public:
    int howManyWays(vector <string> board, int k) {
        cout << "TEST" << endl;
        vector<P> path;
        path.push_back(P(0, 0));
        S.clear();
        shape.clear();
        createShape(k, 1, path);
        for (auto el : S) {
            if (el.size() == k) {
                shape.push_back(el);
            }
        }
        cout << S.size() << endl;
        cout << shape.size() << endl;
        return howMany(board);
    }
};