SRM 651 div2 hard:FoxConnection4
同じ回のdiv1medと同じ発想だったので早く解けてよかったのだが、mod 1000000009に惑わされて結構時間がかかった。
問題:一部のセルが埋められたH*Wの2次元グリッドが与えられる。空白セルのうち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); } };