Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- int btod(string number)
- {
- int base=1;
- int dec=0;
- int i=number.length()-1;
- while(i>=0)
- {
- int rem=number[i]-'0';
- dec+=rem*base;
- base=base*2;
- i--;
- }
- return dec;
- }
- int findans(vector<vector<int>> v,vector<int>& check,int cnt,int i,int j,vector<int>& dp)
- {
- if(cnt==v.size() && i==-1)
- {
- return 1;
- }
- if(j<0)
- {
- return 0;
- }
- int value=-1;
- int number=0;
- string val="";
- if(v[i][j] && !check[j])
- {
- //cout<<"For i = "<<i<<" and j = "<<j<<endl;
- check[j]=1;
- for(int k=0;k<check.size();k++)
- {
- char c='0'+check[k];
- val+=c;
- //cout<<c<<" ";
- }
- //cout<<endl;
- // cout<<"Number = "<<number<<endl;
- check[j]=0;
- value=btod(val);
- //cout<<value<<endl;
- }
- if(dp[value]!=-1 && value!=-1)
- {
- return dp[value];
- }
- if(v[i][j]==1 && check[j]!=1)
- {
- check[j]=1;
- int sum=findans(v,check,cnt+1,i-1,v.size()-1,dp);
- check[j]=0;
- // cout<<"Sum is "<<sum<<endl;
- return dp[value]=sum+findans(v,check,cnt,i,j-1,dp);
- }
- return findans(v,check,cnt,i,j-1,dp);
- }
- int32_t main()
- {
- clock_t tStart = clock();
- int t;
- cin>>t;
- while(t--)
- {
- int n;
- cin>>n;
- vector<vector<int>> v(n,vector<int>(n,0));
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- int x;
- cin>>x;
- v[i][j]=x;
- }
- }
- vector<int> check(n,0);
- vector<int> dp(10000000,-1);
- int ans=findans(v,check,0,v.size()-1,v.size()-1,dp);
- cout<<ans<<endl;
- printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
- }
- }
Add Comment
Please, Sign In to add comment