Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- typedef long long ll;
- typedef vector<ll> vi;
- typedef pair<ll, ll> pii;
- #define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
- #define repf(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
- #define rrep(i, n) for (ll i = (n)-1; i >= 0; --i)
- #define rrepf(i, a, n) for (ll i = (n)-1; i >= a; --i)
- #define all(v) (v).begin(), (v).end()
- #ifdef ON99
- #include "debug.h"
- #else
- #define debug(...) 69
- #endif
- ll dp[31][1 << 15][5];
- bool obs[31][16];
- ll obsb[31];
- ll n, m, k;
- const ll M = 1e9 + 7;
- bool occ(ll mask, ll j)
- {
- if (j >= m)
- return 1;
- return !!(mask & (1 << j));
- }
- // 1 in mask represents occupied
- void sol(ll i, ll j, ll mask, ll next_mask, ll cur_k, ll next_k)
- {
- if (j == m)
- {
- dp[i + 1][next_mask][next_k] += dp[i][mask][cur_k];
- dp[i + 1][next_mask][next_k] %= M;
- debug(i + 1, next_mask, next_k, dp[i + 1][next_mask][next_k]);
- return;
- }
- // trying to fill current column
- // already occupied
- if (occ(mask, j))
- {
- sol(i, j + 1, mask, next_mask, cur_k, next_k);
- return;
- }
- // put horizontal and 2x2
- if (!occ(mask, j + 1))
- {
- sol(i, j + 2, mask, next_mask, cur_k, next_k);
- if (!obs[i + 1][j] && !obs[i + 1][j + 1] && next_k < k)
- sol(i, j + 2, mask, next_mask | (3 << j), cur_k, next_k + 1);
- }
- // put vertical
- if (!obs[i + 1][j])
- sol(i, j + 1, mask, next_mask | (1 << j), cur_k, next_k);
- }
- void solve(int _tc)
- {
- cin >> n >> m >> k;
- rep(i, n)
- {
- rep(j, m)
- {
- char c;
- cin >> c;
- obs[i][j] = c == '#';
- obsb[i] |= obs[i][j] << j;
- }
- }
- rep(cur_k, k + 1)
- dp[0][obsb[0]][cur_k] = 1;
- rep(i, n)
- rep(mask, 1 << m)
- rep(cur_k, k + 1)
- sol(i, 0, mask, obsb[i + 1], cur_k, cur_k);
- cout << dp[n][0][k] << '\n';
- }
- // think twice, code once
- int main()
- {
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int tc = 1;
- // cin >> tc;
- rep(i, tc)
- solve(i);
- }
Advertisement
Add Comment
Please, Sign In to add comment