Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- My code works like:
- If any tile spans next row than we must bit on how many columns it spans in next row.than we must go to
- 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
- more than one column according to previous condion but our nest cell of this column is empty.than we have to use
- a flag to handle this case.*/
- #include<bits/stdc++.h>
- using namespace std;
- #define ull unsigned long long
- 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];
- int bitCheck(int a,int k) {return ((bool)(a&(1<<(k))));}
- int bitoff(int a,int k) { return a=(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)));}
- ull giveres(int row,int col,int mask,string s,int flag=0)
- {
- // cout<<s<<endl;
- if(row>=n)
- {
- //cout<<s<<endl;
- return 1;
- }
- if(vis[row][col][mask][flag]==cas)return dp[row][col][mask][flag];
- vis[row][col][mask][flag]=cas;
- ull ret=0;
- if(col>=m)
- {
- //cout<<"mali "<<s<<endl;
- ret+= giveres(row+1,0,masks[row+1]|mask,s);
- }
- else if(flag)
- {
- ///tiles 2
- if(col+1<m&&bitCheck(mask,col+1)==0)
- ret+=giveres(row,col+2,mask,s+'2');
- ///tiles 6
- if(row+1<n&&col+1<m&&bitCheck(mask,col+1)==0&&bitCheck(masks[row+1],col+1)==0)
- {
- ret+=giveres(row,col+2,bitOn(mask,col+1),s+'6');
- }
- }
- else if(bitCheck(mask,col)==1)
- {
- //cout<<"calu "<<s<<endl;
- ret+= giveres(row,col+1,bitoff(mask,col),s);
- }
- else{
- ///tiles 1
- if(row+1<n&&bitCheck(masks[row+1],col)==0)
- ret+=giveres(row,col+1,bitOn(mask,col),s+'1');
- ///tiles 2
- if(col+1<m&&bitCheck(mask,col+1)==0)
- ret+=giveres(row,col+2,mask,s+'2');
- ///tiles 3
- if(row+1<n&&col+1<m&&bitCheck(masks[row+1],col)==0&&bitCheck(masks[row+1],col+1)==0)
- {
- if(bitCheck(mask,col+1)==1)
- {
- ret+=giveres(row,col+2,bitOn(mask,col+1)|bitOn(mask,col),s+'3');
- }
- else
- //cout<<"3 "<<tmp<<endl;
- ret+=giveres(row,col+1,bitOn(mask,col+1)|bitOn(mask,col),s+'3',1);
- }
- ///tiles 4
- if(row+1<n&&col+1<m&&bitCheck(masks[row+1],col)==0&&bitCheck(mask,col+1)==0)
- {
- ret+=giveres(row,col+2,bitOn(mask,col),s+'4');
- }
- ///tiles 5
- if(row+1<n&&col>0&&bitCheck(masks[row+1],col-1)==0&&bitCheck(masks[row+1],col)==0&&bitCheck(mask,col-1)==0)
- {
- //cout<<5<<" "<<col<<" "<<mask<<endl;
- ret+=giveres(row,col+1,bitOn(mask,col)|bitOn(mask,col-1),s+'5');
- }
- ///tiles 6
- if(row+1<n&&col+1<m&&bitCheck(mask,col+1)==0&&bitCheck(masks[row+1],col+1)==0)
- {
- ret+=giveres(row,col+2,bitOn(mask,col+1),s+'6');
- }
- }
- return dp[row][col][mask][flag]=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: %llu\n",q+1,giveres(0,0,masks[0],""));
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment