D - Hanjo Editorial by en_translator
Since the constraints are small, where \(HW \le 16\), so let us consider searching the way of covering exhaustively.
Starting from the top-left cell, perform DFS of trying placing a square tatami mat, a rectangular tatami mat that sticks out either to the left or below; then we can exhaustively search all the ways of covering.
Now let’s estimate the time complexity.
We have the choices of the top-left cell and the direction of tatami mats, so we have the upper bound of answer of \(2^A\binom{HW}A\).
Since \(HW2^A\binom{HW}A\) is at most \(5 \times 10^7\), so it is fast enough.
In fact, the maximum answer is \(3388\),
so it works much faster than estimated.
BONUS: Solve for \(HW ≤ 200\)!
Sample Code (C++)
#include <iostream>
using namespace std;
int H, W, A, B, ans = 0;
void dfs(int i, int bit, int A, int B){
if(i == H * W) return (void)ans++;
if(bit & 1 << i) return dfs(i + 1, bit, A, B);
if(B) dfs(i + 1, bit | 1 << i, A, B - 1);
if(A){
if(i % W != W - 1 && ~bit & 1 << (i + 1)) dfs(i + 1, bit | 1 << i | 1 << (i + 1), A - 1, B);
if(i + W < H * W) dfs(i + 1, bit | 1 << i | 1 << (i + W), A - 1, B);
}
}
int main(){
cin >> H >> W >> A >> B;
dfs(0, 0, A, B);
cout << ans << endl;
}
Sample Code (Python)
H, W, A, B = map(int, input().split())
ans = 0
def dfs(i, bit, A, B):
if i == H * W:
global ans
ans += 1
return
if bit >> i & 1:
dfs(i + 1, bit, A, B)
return
if B:
dfs(i + 1, bit | 1 << i, A, B - 1)
if A:
if i % W != W - 1 and not bit & 1 << (i + 1):
dfs(i + 1, bit | 1 << i | 1 << (i + 1), A - 1, B)
if i + W < H * W:
dfs(i + 1, bit | 1 << i | 1 << (i + W), A - 1, B)
dfs(0, 0, A, B)
print(ans)
posted:
last update: