RaFiN_

broken profile dp code

Jun 13th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.69 KB | None | 0 0
  1.  
  2.  
  3. /**
  4.  
  5. My code works like:
  6.     If any tile spans next row than we must bit on how many columns it spans in next row.than we must go to
  7.     current column+that number of columns of the next row.Other wise it will not work properly.But there is a case when we have to go
  8.     more than one column according to previous condion but our nest cell of this column is empty.than we have to use
  9.     a flag to handle this case.*/
  10.  
  11.  
  12.  
  13.  
  14.  
  15. #include<bits/stdc++.h>
  16. using namespace std;
  17. #define ull unsigned long long
  18.  
  19. int cas,vis[102][9][(1<<8)+5][2];ull dp[102][9][(1<<8)+5][2];int n,m,masks[102];char str[105][105];
  20.  
  21. int         bitCheck(int a,int k)     {return ((bool)(a&(1<<(k))));}
  22. int         bitoff(int a,int k)    {   return a=(a&(~(1<<(k)))) ;}
  23. int         bitOn(int a,int k)      { return  a=(a|(1<<(k)));}
  24. int          Reset(int a,int k)  { return    a=(a^(1<<(k)));}
  25.  
  26. ull giveres(int row,int col,int mask,string s,int flag=0)
  27. {
  28.    // cout<<s<<endl;
  29.     if(row>=n)
  30.     {
  31.         //cout<<s<<endl;
  32.         return 1;
  33.     }
  34.     if(vis[row][col][mask][flag]==cas)return  dp[row][col][mask][flag];
  35.     vis[row][col][mask][flag]=cas;
  36.     ull ret=0;
  37.     if(col>=m)
  38.     {
  39.         //cout<<"mali "<<s<<endl;
  40.         ret+= giveres(row+1,0,masks[row+1]|mask,s);
  41.     }
  42.     else if(flag)
  43.     {
  44.         ///tiles 2
  45.         if(col+1<m&&bitCheck(mask,col+1)==0)
  46.             ret+=giveres(row,col+2,mask,s+'2');
  47.         ///tiles 6
  48.         if(row+1<n&&col+1<m&&bitCheck(mask,col+1)==0&&bitCheck(masks[row+1],col+1)==0)
  49.         {
  50.             ret+=giveres(row,col+2,bitOn(mask,col+1),s+'6');
  51.         }
  52.  
  53.     }
  54.     else if(bitCheck(mask,col)==1)
  55.     {
  56.         //cout<<"calu "<<s<<endl;
  57.         ret+= giveres(row,col+1,bitoff(mask,col),s);
  58.     }
  59.     else{
  60.         ///tiles 1
  61.         if(row+1<n&&bitCheck(masks[row+1],col)==0)
  62.             ret+=giveres(row,col+1,bitOn(mask,col),s+'1');
  63.         ///tiles 2
  64.         if(col+1<m&&bitCheck(mask,col+1)==0)
  65.             ret+=giveres(row,col+2,mask,s+'2');
  66.         ///tiles 3
  67.         if(row+1<n&&col+1<m&&bitCheck(masks[row+1],col)==0&&bitCheck(masks[row+1],col+1)==0)
  68.         {
  69.             if(bitCheck(mask,col+1)==1)
  70.             {
  71.                 ret+=giveres(row,col+2,bitOn(mask,col+1)|bitOn(mask,col),s+'3');
  72.             }
  73.             else
  74.             //cout<<"3 "<<tmp<<endl;
  75.             ret+=giveres(row,col+1,bitOn(mask,col+1)|bitOn(mask,col),s+'3',1);
  76.         }
  77.         ///tiles 4
  78.         if(row+1<n&&col+1<m&&bitCheck(masks[row+1],col)==0&&bitCheck(mask,col+1)==0)
  79.         {
  80.             ret+=giveres(row,col+2,bitOn(mask,col),s+'4');
  81.         }
  82.         ///tiles 5
  83.         if(row+1<n&&col>0&&bitCheck(masks[row+1],col-1)==0&&bitCheck(masks[row+1],col)==0&&bitCheck(mask,col-1)==0)
  84.         {
  85.             //cout<<5<<" "<<col<<" "<<mask<<endl;
  86.             ret+=giveres(row,col+1,bitOn(mask,col)|bitOn(mask,col-1),s+'5');
  87.         }
  88.         ///tiles 6
  89.         if(row+1<n&&col+1<m&&bitCheck(mask,col+1)==0&&bitCheck(masks[row+1],col+1)==0)
  90.         {
  91.             ret+=giveres(row,col+2,bitOn(mask,col+1),s+'6');
  92.         }
  93.  
  94.     }
  95.     return dp[row][col][mask][flag]=ret;
  96. }
  97.  
  98. int main()
  99. {
  100.  
  101.     int t;
  102.     scanf("%d",&t);
  103.     for(int q=0;q<t;q++)
  104.     {
  105.         scanf("%d%d",&n,&m);
  106.         for(int i=0;i<n;i++)scanf("%s",str[i]);
  107.         memset(masks,0,sizeof(masks));
  108.         if(m<=n)
  109.         {
  110.             for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(str[i][j]=='#')masks[i]=bitOn(masks[i],j);
  111.         }
  112.         else {
  113.             for(int j=0;j<m;j++)for(int i=0;i<n;i++)if(str[i][j]=='#')masks[j]=bitOn(masks[j],i);
  114.             swap(n,m);
  115.         }
  116.         cas++;
  117.         printf("Case %d: %llu\n",q+1,giveres(0,0,masks[0],""));
  118.  
  119.     }
  120.  
  121.     return 0;
  122. }
Add Comment
Please, Sign In to add comment