forked from apaarkamal/competitive_september_2k19
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ASSIGN_SPOJ.cpp
46 lines (40 loc) · 860 Bytes
/
ASSIGN_SPOJ.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define F first
#define S second
#define P pair<int,int>
#define pb push_back
const int N = 21;
int a[N][N], res, n, memo[N][1 << N];
int solve(int row, int mask) {
if (row == n) {
return 1;
}
if (memo[row][mask] != -1) return memo[row][mask];
int ans = 0;
for (int col = 0; col < n; col++) {
if (a[row][col] && !((mask >> col) & 1)) {
ans += solve(row + 1, mask ^ (1 << col));
}
}
return memo[row][mask] = ans;
}
int32_t main()
{
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t; cin >> t; while (t--)
{
int i, j, k, m, ans = 0, cnt = 0, sum = 0;
cin >> n;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
cin >> a[i][j];
}
}
memset(memo, -1, sizeof(memo));
cout << solve(0, 0) << '\n';
}
}