解法
回転と裏返しも良いと書いてあるが，裏返しは意味がない． 回転が高々 \(2^{N}\) 通り， 埋める順番が高々 \(N!\) 通り． \(N \leq 7\) なので，遷移に時間が多少掛かっても間に合う．
判定問題を試すときは，取りこぼしさえ無ければ十分． 数え上げ問題の場合は，取りこぼしがないだけでなく，重複も取り除かないといけない． 今回は判定問題なので，重複しても良い． 左上のマスから全探索して，長方形の左上を置くことにする． これを，並べ替え \(N!\) と回転 \(2^{N}\) に対して行う．
実装
DFSで実装した． next_permutation と bitmask でも可能．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,h,w;
cin >> n >> h >> w;
rep(i,n){
cin >> ab[i].first >> ab[i].second;
}
ll sx = -1, sy = -1;
[&](){
rep(x,h) rep(y,w) if(s[x][y] == '.'){
sx = x;
sy = y;
// break; // 一つしか for を抜けない
return ;
}
}();
if(sx == -1) return true;
bool any = true;
rep(i,used.size()) any &= used[i];
if(any) return false;
// rectangle
rep(ri,n) if(!used[ri]){ // used 判定
auto [a,b] = ab[ri];
rep(flip, 2){
swap(a,b);
B ns = s;
bool ok = [&]() -> bool {
if(sx + a > h) return false;
if(sy + b > w) return false;
rep(xi, a) rep(yi, b){
ll nx = sx + xi;
ll ny = sy + yi;
if(ns[nx][ny] != '.') return false;
ns[nx][ny] = '#';
}
return true;
}();
if(ok){
used[ri] = true;
if(dfs(dfs, ns, used)) return true;
used[ri] = false;
}
}
}
return false;
};
B s(h, string(w,'.'));
yesno(dfs(dfs, s, used));
return 0;
}
