daily pastebin goal
7%
SHARE
TWEET

Untitled

Wazedrifat Jun 13th, 2018 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define PII pair<int, int>
  5. #define MX 9
  6. #define ll long long int
  7. #define MOD 1//(((ll)1<<64)-1)
  8. #define bit bitset<10>
  9.  
  10. int n, m, total, flag[10][100], num[10][100], block[6], cost[6]={2, 2, 3, 3, 3, 3};
  11. ll dp[(1<<10)][100][100];
  12.  
  13. int next(int mask)
  14. {
  15. //  mask=mask&(~(1<<(m+1)));
  16.     mask=mask<<1;
  17.     return mask;
  18. //  bit b=mask;
  19. //  return (int)b.to_ulong();
  20. }
  21.  
  22. ll rec(int mask=0, int r=0, int c=0, int sum=0)
  23. {
  24.     if(flag[r][c])
  25.     {
  26.         mask=mask|1;
  27.         sum++;
  28.     }
  29. //  cout<<"r="<<r<<" c="<<c<<" mask="<<mask<<" "<<bit(mask)<<" sum="<<sum<<endl;
  30.  
  31.     if(r>=n)
  32.     {
  33. //      cout<<"return r="<<r<<" c="<<c<<" mask="<<bit(mask)<<" ret="<<(sum==m*m)<<endl;
  34.         if(sum==n*m)    return 1;
  35.         return 0;
  36.     }
  37.     ll x=-1;
  38. //  cout<<" mask="<<mask<<" bit="<<bit(mask)<<" r="<<r<<" c="<<c<<" x="<<x<<" dp=";
  39. //  int m=(1<<11)-1;    m=mask&m;
  40. //  ll &d=dp[mask][r][c];
  41. //  cout<<d<<endl;
  42. //  if(d!=x)    return d;
  43.  
  44. //  cout<<"prev r="<<r<<" c="<<c<<endl;
  45.     int r1=r, c1=c;
  46.     c1=(c+1)%m;
  47.     if(!c1) r1++;
  48. //  cout<<"next r="<<r<<" c="<<c<<endl;
  49.  
  50.     ll cnt=rec(next(mask), r1, c1, sum);
  51.  
  52.     for(int i=0 ; i<6 ; i++)
  53.     {
  54.         if( !(mask&block[i]) && ( (i==0&&r>0)||(i==1&&c>0)||(i==2&&r>0&&c>0)||(i==3&&c<m-1&&r>0)||(i==4&&c>0&&r>0)||(i==5&&r>0&&c>0) ) )
  55.         {
  56.  
  57. //          cout<<"mask=\t"<<bit(mask)<<endl<<"block=\t"<<bit(block[i])<<endl<<"ans=\t"<<bit(mask|block[i])<<" "<<!(mask&block[i])<<endl<<endl;
  58. //          cout<<"r1="<<r1<<" c1="<<c1<<" i="<<i<<" mask="<<bit(mask)<<" sum="<<sum<<"->"<<sum+cost[i]<<endl;
  59.             cnt+=rec(next(mask|block[i]) , r1, c1, sum+cost[i]);
  60.         }
  61.     }
  62. //  cout<<"r="<<r<<" c="<<c<<" mask="<<bit(mask)<<" sum="<<sum<<" dp="<<cnt<<endl;
  63.     return cnt;
  64. }
  65.  
  66. int main()
  67. {
  68.     freopen("input.txt", "r", stdin);
  69.     int test;
  70.     cin>>test;
  71.  
  72.     for(int t=1 ; t<=test ; t++)
  73.     {
  74.         memset(flag, 0, sizeof flag);
  75.         memset(num, 0, sizeof num);
  76.         memset(dp, (ll)-1, sizeof dp);
  77.         cin>>n>>m;
  78.  
  79.         char ch[105][105];
  80.         for(int i=0 ; i<n ; i++)
  81.         for(int j=0 ; j<m ; j++)
  82.             cin>>ch[i][j];
  83.  
  84.         if(m>8)
  85.         {
  86.             swap(n, m);
  87.             for(int i=0 ; i<n ; i++)
  88.             for(int j=i+1 ; j<m ; j++)
  89.                 swap(ch[i][j], ch[j][i]);
  90.         }
  91.  
  92.         for(int i=0 ; i<n ; i++)
  93.         for(int j=0 ; j<m ; j++)
  94.             if(ch[i][j]=='#')
  95.             flag[i][j]=1;
  96.  
  97.         block[0]=1|(1<<m);
  98.         block[1]=3;
  99.         block[2]=3|(1<<(m+1));
  100.         block[3]=1|(1<<m);  block[3]|=(1<<(m-1));
  101.         block[4]=3|(1<<m);
  102.         block[5]=1|(1<<m);  block[5]|=(1<<(m+1));
  103. //      total=n*m-c;
  104.  
  105. //      cout<<"total="<<total<<endl;
  106.         cout<<"Case "<<t<<": "<<rec()<<endl;
  107.     }
  108. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top