Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int cas,vis[102][9][(1<<8)+5],dp[102][9][(1<<8)+5],n,m,masks[102];char str[105][105];
- int bitCheck(int a,int k) {return ((bool)(a&(1<<(k))));}
- int bitoff(int a,int k) { return (a&(~(1<<(k)))) ;}
- int bitOn(int a,int k) { return a=(a|(1<<(k)));}
- int Reset(int a,int k) { return a=(a^(1<<(k)));}
- int giveres(int row,int col,int mask)
- {
- if(row>=n)return 1;
- if(vis[row][col][mask]==cas)return dp[row][col][mask];
- vis[row][col][mask]=cas;
- int ret=0;
- if(col>=m)ret+=giveres(row+1,0,masks[row+1]|mask);
- else if(bitCheck(mask,col)==1)ret+=giveres(row,col+1,bitoff(mask,col));
- else{
- ///tiles 1
- if(row+1<n&&bitCheck(masks[row+1],col)==0)
- ret+=giveres(row,col+1,bitOn(mask,col));
- ///tiles 2
- if(col+1<m&&bitCheck(mask,col+1)==0)
- ret+=giveres(col+2,row,mask);
- ///tiles 3
- if(col+1<m&&row+1<n&&bitCheck(masks[row+1],col)==0&&bitCheck(masks[row+1],col+1)==0)
- {
- int tmp=bitOn(mask,col)|bitOn(mask,col+1);
- ret+=giveres(col+1,row,tmp);
- }
- ///tiles 4
- if(col+1<m&&row+1<n&&bitCheck(masks[row+1],col)==0&&bitCheck(mask,col+1)==0)
- {
- ret+=giveres(col+2,row,bitOn(mask,col));
- }
- ///tiles 5
- if(col>0&&row+1<n&&bitCheck(masks[row+1],col-1)==0&&bitCheck(masks[row+1],col==0))
- {
- ret+=giveres(col+1,row,bitOn(mask,col)|bitOn(mask,col-1));
- }
- ///tiles 6
- 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)
- {
- ret+=giveres(col+2,row,bitOn(mask,col+1));
- }
- }
- return dp[col][row][mask]=ret;
- }
- int main()
- {
- int t;
- scanf("%d",&t);
- for(int q=0;q<t;q++)
- {
- scanf("%d%d",&n,&m);
- for(int i=0;i<n;i++)scanf("%s",str[i]);
- memset(masks,0,sizeof(masks));
- if(m<=n)
- {
- for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(str[i][j]=='#')masks[i]=bitOn(masks[i],j);
- }
- else {
- for(int j=0;j<m;j++)for(int i=0;i<n;i++)if(str[i][j]=='#')masks[j]=bitOn(masks[j],i);
- swap(n,m);
- }
- cas++;
- printf("Case %d: %d\n",q+1,giveres(0,0,masks[0]));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement