「超 大 作」。
枝狩りがうまくできなかったので先輩の手助けなどを借りた。とっても感謝。
とりあえずしたこと。気が狂う感じだった。
- 入力制約よく分からないので色々対策
- まあ当然元々の'.'とパーツの'#'の個数照合して不一致だったら即NOを返す。(これをすることで全部埋まったかどうかのチェックもしなくて良い)
- 一行毎にbitを使い、判定等をO(20^2) ⇒ O(20)に。
- [何番目までパーツを確定したか][現在の埋まり状況]で申し訳程度のメモ化(setを用いる。)
- 残りのパーツでどうあがいても絶望な場合(埋められない箇所がある)はやめに枝狩り←最重要
このコードは嬉しかったから貼るだけで、読ませる気がないので、質問とかあったら気軽にコメントでお願いします。
#include <iostream> #include <vector> #include <algorithm> #include <deque> #include <set> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define all(n) n.begin(),n.end() typedef long long ll; int bx[20]; int xbit[10][4][20]; int H[10][4],W[10][4]; int pzlCnt[10]; int num[10]; int h,w,P; int v[10]; int generate(int _bx[20],deque<string> t,char del,int &_H,int &_W){ rep(i,20) _bx[i] = 0; while(count(all(t[0]),del) == t[0].size()) t.pop_front(); while(count(all(t[t.size()-1]),del) == t[t.size()-1].size()) t.pop_back(); while(1){ bool f = true; rep(i,t.size()) f &= t[i][0] == del; if(f) rep(i,t.size()) t[i] = t[i].substr(1); else break; } while(1){ bool f = true; rep(i,t.size()) f &= t[i][t[i].size()-1] == del; if(f) rep(i,t.size()) t[i] = t[i].erase(t[i].size()-1); else break; } int H = t.size() , W = t[0].length(); rep(i,H)rep(j,W) _bx[i] |= ( (t[i][j]=='#') << j); _W = W , _H = H; } string genString(char c,int l){ string ans; rep(i,l)ans += c; return ans; } void fix(deque<string> &t){ int mxsz = max(t.size(),t[0].size()); rep(i,t.size()) while(t[i].size() < mxsz) t[i] += '.'; while(t.size() < mxsz) t.push_back(genString('.',mxsz)); } void rotate(deque<string> &t){ rep(i,t.size()) rep(j,i) swap(t[i][j],t[j][i]); rep(i,t.size()) reverse(all(t[i])); } bool isok(int ax[20],int tx[20],int x,int y){ rep(i,20) if(ax[i+y] & (tx[i] << x) )return false; return true; } void add(int a[20],int b[20],int x,int y){rep(i,20) a[i+y] |= (b[i]<<x);} void sub(int a[20],int b[20],int x,int y){rep(i,20) a[i+y] &= ~(b[i]<<x);} struct NODE{ int v[20]; NODE(int a[20]){rep(i,20)v[i] = a[i];} }; bool operator < (const NODE &a, const NODE& b){ rep(i,20)if(a.v[i] != b.v[i]) return a.v[i] < b.v[i]; return false; } set<NODE> memo[10]; int dfs(int k , int cx[20]){ if(k == P)return true; NODE key(cx); if(memo[k].find(key) != memo[k].end())return false; else memo[k].insert(key); int cur = v[k]; int pre[20]={0}; for(int f=k;f<P;f++){ int c = v[f]; rep(d,4){ rep(i,h-H[c][d]+1){ rep(j,w-W[c][d]+1){ if( isok(cx,xbit[c][d],j,i) ){ add(pre,xbit[c][d],j,i); } } } } } rep(i,h){ if( pre[i] != ((~cx[i]) & ((1<<w)-1)) ) return false; } rep(d,4){ rep(i,h-H[cur][d]+1){ rep(j,w-W[cur][d]+1){ if( isok(cx,xbit[cur][d],j,i) ){ add(cx,xbit[cur][d],j,i); if(dfs(k+1,cx)) return true; sub(cx,xbit[cur][d],j,i); } } } } return false; } int _2dCount(deque<string> &t,char c){ int ans = 0; rep(i,t.size())rep(j,t[i].size()) ans += t[i][j] == c; return ans; } int main(){ string t; deque<string> tmp; while(cin >> h >> w && h || w){ rep(i,10)num[i] = i; tmp.clear(); rep(i,h)cin >> t , tmp.push_back(t); generate(bx,tmp,'-',h,w); int allCnt = _2dCount(tmp,'.'); int N; cin >> N; rep(k,N){ tmp.clear(); int th,tw; cin >> th >> tw; rep(i,th)cin >> t , tmp.push_back(t); pzlCnt[k] = _2dCount(tmp,'#'); fix(tmp); rep(d,4){ generate(xbit[k][d] , tmp , '.' , H[k][d] , W[k][d]); rotate(tmp); } } int Q; cin >> Q; rep(x,Q){ rep(i,10)memo[i].clear(); int qCnt = 0; int tmpField[20]; rep(i,20)tmpField[i] = bx[i]; cin >> P; rep(j,P) cin >> v[j] , v[j] = find(num,num+10,v[j]-1)-num , qCnt += pzlCnt[v[j]]; if(qCnt == allCnt && dfs(0,tmpField)){ cout << "YES" << endl; }else{ cout << "NO" << endl; } } } }
