Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

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