daily pastebin goal
33%
SHARE
TWEET

Untitled

a guest Jun 13th, 2018 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ull unsigned long long
  4.  
  5. int cas,vis[102][9][(1<<8)+5];ull dp[102][9][(1<<8)+5];int n,m,masks[102];char str[105][105];
  6.  
  7. int         bitCheck(int a,int k)     {return ((bool)(a&(1<<(k))));}
  8. int         bitoff(int a,int k)    {   return (a&(~(1<<(k)))) ;}
  9. int         bitOn(int a,int k)      { return  a=(a|(1<<(k)));}
  10. int          Reset(int a,int k)  { return    a=(a^(1<<(k)));}
  11.  
  12. ull giveres(int row,int col,int mask)
  13. {
  14.     if(row>=n)return 1;
  15.     if(vis[row][col][mask]==cas)return dp[row][col][mask];
  16.     vis[row][col][mask]=cas;
  17.     ull ret=0;
  18.     if(col>=m)ret+=giveres(row+1,0,masks[row+1]|mask);
  19.     else if(bitCheck(mask,col)==1)ret+=giveres(row,col+1,bitoff(mask,col));
  20.     else{
  21.         ///tiles 1
  22.         if(row+1<n&&bitCheck(masks[row+1],col)==0)
  23.             ret+=giveres(row,col+1,bitOn(mask,col));
  24.         ///tiles 2
  25.         if(col+1<m&&bitCheck(mask,col+1)==0)
  26.             ret+=giveres(col+2,row,mask);
  27.         ///tiles 3
  28.         if(col+1<m&&row+1<n&&bitCheck(masks[row+1],col)==0&&bitCheck(masks[row+1],col+1)==0)
  29.         {
  30.             int tmp=bitOn(mask,col)|bitOn(mask,col+1);
  31.             ret+=giveres(col+1,row,tmp);
  32.         }
  33.         ///tiles 4
  34.         if(col+1<m&&row+1<n&&bitCheck(masks[row+1],col)==0&&bitCheck(mask,col+1)==0)
  35.         {
  36.             ret+=giveres(col+2,row,bitOn(mask,col));
  37.         }
  38.         ///tiles 5
  39.         if(col>0&&row+1<n&&bitCheck(masks[row+1],col-1)==0&&bitCheck(masks[row+1],col==0))
  40.         {
  41.             ret+=giveres(col+1,row,bitOn(mask,col)|bitOn(mask,col-1));
  42.         }
  43.         ///tiles 6
  44.         if(row+1<n&&col+1<m&&bitCheck(masks[row],col+1)==0&&bitCheck(masks[row+1],col+1)==0&&bitCheck(mask,col+1)==0)
  45.         {
  46.             ret+=giveres(col+2,row,bitOn(mask,col+1));
  47.         }
  48.  
  49.     }
  50.     return dp[row][col][mask]=ret;
  51. }
  52.  
  53. int main()
  54. {
  55.  
  56.     int t;
  57.     scanf("%d",&t);
  58.     for(int q=0;q<t;q++)
  59.     {
  60.         scanf("%d%d",&n,&m);
  61.         for(int i=0;i<n;i++)scanf("%s",str[i]);
  62.         memset(masks,0,sizeof(masks));
  63.         if(m<=n)
  64.         {
  65.             for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(str[i][j]=='#')masks[i]=bitOn(masks[i],j);
  66.         }
  67.         else {
  68.             for(int j=0;j<m;j++)for(int i=0;i<n;i++)if(str[i][j]=='#')masks[j]=bitOn(masks[j],i);
  69.             swap(n,m);
  70.         }
  71.         cas++;
  72.         printf("Case %d: %llu\n",q+1,giveres(0,0,masks[0]));
  73.  
  74.     }
  75.  
  76.     return 0;
  77. }
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