Submission #21090436

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define TIME 1.0*clock()/CLOCKS_PER_SEC
#define pii pair < int , int >
#define Endl '\n'
#define endl '\n'

#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

template <typename T> using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 7;
const int FFTM = 2e9 + 9;

const int SX[4] = {0 , 1 ,  - 1 , 0};
const int SY[4] = {1 , 0 , 0 ,  - 1};
const int rx[8] = {1,  - 1, 0, 0, 1, 1, -1, -1};
const int ry[8] = {0, 0, 1,  - 1, 1,  - 1, 1, -1};
const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};

typedef cc_hash_table< int, int, hash<int>, equal_to<int>, direct_mask_range_hashing<int>, hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>> ht;

int n, m, a, b;

int can[(int)pow(3, 16) + 10];

int c[17][17];

bool ok(int x, int y){
    return x >= 0 && x <= n - 1 && y >= 0 && y <= m - 1;
}

void get_(int mask){
     for (int i = n - 1;i >= 0; --i){
        for (int j = m - 1;j >= 0; --j){
            c[i][j] = mask % 3;
            mask /= 3;
        }
    }
}

int ans = 0;

void go(int mask, int kol = 0){
    if (can[mask])return;
    can[mask] = 1;
    if (kol == a){
        ans++;

//        for (int i = 0;i < n; ++i){
//            for (int j = 0;j < m; ++j){
//                cout << c[i][j] << " ";
//            }
//            cout << endl;
//        }
//        cout << endl;

        return;
    }
    for (int i = 0;i < n; ++i){
        for (int j = 0;j < m; ++j){
            if (c[i][j] == 0){

                for (int k = 0;k < 4; ++k){
                    int ni = i + SX[k];
                    int nj = j + SY[k];
                    if (ok(ni, nj) && c[ni][nj] == 0){
                        c[i][j] = c[ni][nj] = (k == 0 || k == 3 ? 1 : 2);


                        int nw_mask = 0;
                        for (int i1 = 0;i1 < n; ++i1){
                            for (int j1 = 0;j1 < m; ++j1){
                                nw_mask *= 3;
                                nw_mask += c[i1][j1];
                            }
                        }
                        go(nw_mask, kol + 1);

                        c[i][j] = c[ni][nj] = 0;


                    }
                }

            }
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("domino-covering-1.in", "r", stdin);
//    freopen("domino-covering-1.out", "w", stdout);
#endif
    cin >> n >> m >> a >> b;
    if (n > m)swap(n, m);
    go(0);
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result