Guest User

Untitled

a guest
Oct 26th, 2022
197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.97 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector<ll> vi;
  6. typedef pair<ll, ll> pii;
  7. #define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
  8. #define repf(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
  9. #define rrep(i, n) for (ll i = (n)-1; i >= 0; --i)
  10. #define rrepf(i, a, n) for (ll i = (n)-1; i >= a; --i)
  11. #define all(v) (v).begin(), (v).end()
  12.  
  13. #ifdef ON99
  14. #include "debug.h"
  15. #else
  16. #define debug(...) 69
  17. #endif
  18.  
  19. ll dp[31][1 << 15][5];
  20. bool obs[31][16];
  21. ll obsb[31];
  22. ll n, m, k;
  23.  
  24. const ll M = 1e9 + 7;
  25.  
  26. bool occ(ll mask, ll j)
  27. {
  28.     if (j >= m)
  29.         return 1;
  30.     return !!(mask & (1 << j));
  31. }
  32.  
  33. // 1 in mask represents occupied
  34. void sol(ll i, ll j, ll mask, ll next_mask, ll cur_k, ll next_k)
  35. {
  36.     if (j == m)
  37.     {
  38.         dp[i + 1][next_mask][next_k] += dp[i][mask][cur_k];
  39.         dp[i + 1][next_mask][next_k] %= M;
  40.         debug(i + 1, next_mask, next_k, dp[i + 1][next_mask][next_k]);
  41.         return;
  42.     }
  43.     // trying to fill current column
  44.     // already occupied
  45.     if (occ(mask, j))
  46.     {
  47.         sol(i, j + 1, mask, next_mask, cur_k, next_k);
  48.         return;
  49.     }
  50.     // put horizontal and 2x2
  51.     if (!occ(mask, j + 1))
  52.     {
  53.         sol(i, j + 2, mask, next_mask, cur_k, next_k);
  54.         if (!obs[i + 1][j] && !obs[i + 1][j + 1] && next_k < k)
  55.             sol(i, j + 2, mask, next_mask | (3 << j), cur_k, next_k + 1);
  56.     }
  57.     // put vertical
  58.     if (!obs[i + 1][j])
  59.         sol(i, j + 1, mask, next_mask | (1 << j), cur_k, next_k);
  60. }
  61.  
  62. void solve(int _tc)
  63. {
  64.     cin >> n >> m >> k;
  65.     rep(i, n)
  66.     {
  67.         rep(j, m)
  68.         {
  69.             char c;
  70.             cin >> c;
  71.             obs[i][j] = c == '#';
  72.             obsb[i] |= obs[i][j] << j;
  73.         }
  74.     }
  75.     rep(cur_k, k + 1)
  76.         dp[0][obsb[0]][cur_k] = 1;
  77.     rep(i, n)
  78.         rep(mask, 1 << m)
  79.             rep(cur_k, k + 1)
  80.                 sol(i, 0, mask, obsb[i + 1], cur_k, cur_k);
  81.     cout << dp[n][0][k] << '\n';
  82. }
  83.  
  84. // think twice, code once
  85. int main()
  86. {
  87.     // freopen("input.txt", "r", stdin);
  88.     // freopen("output.txt", "w", stdout);
  89.     ios_base::sync_with_stdio(0);
  90.     cin.tie(0);
  91.     int tc = 1;
  92.     // cin >> tc;
  93.     rep(i, tc)
  94.         solve(i);
  95. }
  96.  
Advertisement
Add Comment
Please, Sign In to add comment