Checkerboard problem---[Status Compression]

copyright
This article is original, please refer to the paper Zhou Wei "State Compression of Dynamic Programming" before reading this article

Question 1:
Place nnn rooks (which can attack the row and column where they are located) on a checkerboard of n∗n(n≤20)n*n(n≤20)n∗n(n≤20), and find the ones that cannot attack each other Total number of programs.

If you think about this from a combinatorics perspective, it's pretty simple:

We put it line by line, the first line has nnn choices, the second line has n−1,...n-1,...n−1,..., and the last line has 1 choice. According to the principle of multiplication, the answer is n! n!n!

Here we introduce another solution: State Compressing Recursion (SCR) (States Compressing Recursion, SCR) (States Compressing Recursion, SCR).

We still place line by line.
Take the placement of chess pieces as the state, if a chess piece has been placed in a certain column, it will be 111, otherwise it will be 000. In this way, a state can be represented by a binary number of up to 202020 bits.
For example, n=5n=5n=5, and the 1st, 3rd, 41st, 3rd, 41st, 3rd, and 4th columns have been placed, then this state can be represented as 011010110101101 (from right to left). Let fs be the number of solutions to reach state s, then you can try to establish the recurrence relation of f.
Consider n=5,s=01101n=5,s=01101n=5,s=01101
Because we placed it row by row, when s is reached, the third row has already been placed. And because a row can place only one car, we know that state s must come from:

        ①The first two rows have pawns placed in columns 3 and 4(Regardless of the order, the same below),The third row is placed in column 1; 

        ②The first two rows have pawns placed in columns 1 and 4, and the third row is placed in column 3; 

        ③The first two rows have pawns placed in columns 1 and 3, and the third row is placed in column 4.

    These three cases do not intersect with each other, and only these three cases are possible. According to the principle of addition, fs should be equal to the sum of these three cases. written in recursive             Yes:

     f(01101) = f(01100) + f(01001) + f(00101);

According to the above discussion ideas, the solution of the example is obtained:
f(0) = 1;

    f(s) = ·f(s-2^i);

      in s from right i+1 bit is 1(In fact, it is enumerating s 1 in the binary representation of)

code show as below:

#include<iostream>
#include<cstdio>
using namespace std;
long long f[1<<20];
 
int main(){
    long long n;
    while(cin>>n){
        memset(f,0,sizeof(f));
        f[0] = 1;
        long long i,t;
        for( i=1; i< 1<<n; i++){
            for( t=i; t>0; t -= (t & -t)){
                f[i] += f[i & ~(t & -t)];  //Pay attention to understanding
            }
        }
        cout<<f[(1<<n)-1]<<endl; 
    }
}

Question 2: Place n rooks on the n∗n(n≤20)n*n(n≤20)n∗n(n≤20) checkerboard. Some squares cannot be placed, so they cannot be placed on each other.
The total number of schemes attacked.
Input: give you an n and m, which represent the size of the chessboard and the total number of squares that cannot be placed
Next are m lines of coordinates, representing the seats that cannot be placed.
Output: Total number of eligible schemes.

0 means can be placed, 1 means cannot be placed
0 1 0
0 0 1
0 0 0
enter:
3 2
1 2
2 3
output: 3
enter:
4 1
1 1
Output: 3∗3∗2∗1==183*3*2*1 == 183∗3∗2∗1==18
hint:
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
 
long long f[1<<20];
long long vist[22];
 
int main(){
    long long n,m;
    while(cin>>n>>m){
        memset(f,0,sizeof(f));
        memset(vist,0,sizeof(vist));
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            vist[a] += 1<<(b-1); //A certain position cannot be placed, compress this position into an integer 
        }
        f[0] = 1;
        for(int i=1;i< 1<<n; i++){
            int num = 0;
            for(int j=i;j>0;j -= (j & -j)) num++; //Calculate the number of i state 1, that is, the maximum number of rows included 
            for(int j=i;j>0;j -= (j & -j)) {
                if(!(vist[num]&(j & -j))) f[i] += f[ i& ~(j & -j)];//Determine whether the location can be placed 
            }
        }
        cout<<f[(1<<n)-1]<<endl;
    }
}

Problem 3: Given a checkerboard of n∗mn*mn∗m (n, m≤80,n∗m≤80)(n, m≤80,n*m≤80)(n, m≤80,n∗ m≤80), k(k≤20)k(k≤20)k(k≤20) pieces should be placed on the board so that any two pieces are not adjacent. Find the total number of plans that can be placed

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm> 
using namespace std;
int s[1<<10],c[1<<10],f[82][1<<9][21]; 
int n,m,num,flag,val;
 
void DFS(int ans,int pos,int flag){  ///
	if(pos>n) { 
     	s[++num] = ans; 
     	c[num] = flag;
      	return; 
	}
	DFS(ans,pos+1,flag);
	DFS(ans+(1<<pos-1),pos+2,flag+1);
}
 
int main(){
    while(cin>>n>>m>>val){
        if(n>m) swap(n,m); // row and column exchange 
        num = 0;  // State number initialization  
        DFS(0,1,0); // Parameters: current state, position, number of 1s, find out the total number of eligible conditions in a row 
        memset(f,0,sizeof(f));
        ///
        for(int i=1;i<=num;i++) //The first line is initialized, and the number of 1s in the state is initialized 
        	f[1][s[i]][c[i]] = 1;
        for(int i=2;i<=m;i++){ //which line 
            for(int j=1;j<=num;j++){ //a state of a row 
            	for(int r=1;r<=num;r++){ //a state of the previous line 
            		if(!(s[j]&s[r])){ //The current line and the previous line state do not conflict 
            			for(int k=0;k<=val;k++){ //Enumerate the number of pieces in the current row 
            				if(k>=c[j]) f[i][s[j]][k] += f[i-1][s[r]][k-c[j]]; //Enumerate the current state with the help of the state from the previous line 
            			}
            		}
             	}
            }
        }
        long long sum=0;
        for(int i=1;i<=num;i++) // Accumulates the total number of matches in the last row 
        	sum += f[m][s[i]][val];
       	cout<<sum<<endl;
    }
}

/*
Due to the lack of data, I simulated several sets of data myself
Input: 3 3 2
output: 23
Input: 2 2 2
output: 2
Input: 20 1 2
Output: 171
*/

Question 4:
Put k kings (which can attack the adjacent 888 squares) on the chessboard of n∗n(n≤10)n*n(n≤10)n∗n(n≤10), so that they cannot be
The number of schemes attacking each other.

#include<iostream> 
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
long long f[11][1<<10][30];
int s[1<<10],c[1<<10],num;
int n,m,val;
    
void DFS(int ans,int pos,int flag){
    if(pos>n){
        s[++num] = ans;
        c[num] = flag;
        return ;
    }
    DFS(ans,pos+1,flag);
    DFS(ans+(1<<pos-1),pos+2,flag+1);
}
 
int main(){
    while(cin>>n>>m>>val){
    	num = 0;
    	DFS(0,1,0);
    	memset(f,0,sizeof(f)); 
    	for(int i=1;i<=num;i++)
    	    f[1][s[i]][c[i]]=1;
	    for(int i=2;i<=n;i++){
	        for(int j=1;j<=num;j++){ //current line 
	            for(int r=1;r<=num;r++){ //previous row 
	                if((s[j]&s[r]) || ((s[j]>>1)&s[r]) || ((s[j]<<1)&s[r])) continue; //Eight directions to judge 
	                for(int k=0;k<=val;k++){
	                    if(k>=c[j]) f[i][s[j]][k] += f[i-1][s[r]][k-c[j]];
                 	}
             	}
         	}
     	}
     	long long sum=0;
     	for(int i=1;i<=num;i++)
     		sum += f[n][s[i]][val];
   		cout<<sum<<endl;
    }
}

/*
Input: 3 3 2
Output: 16
Input: 2 2 1
output: 4
Input: 3 3 3
output: 8
Input: 9 9 2
Output: 1968
*/

Problem 5: Given a chessboard of n∗m(n≤100,m≤10)n*m(n≤100,m≤10)n∗m(n≤100,m≤10), some grids cannot place chess pieces . ask for the most
How many pieces are placed on the board so that there are at least two spaces between any two pieces in each row and column.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
long long f[11][1<<10];
int n,m,s[1<<10],c[1<<10];
int num,ant,a[1<<10];
 
void DFS(int ans,int pos,int flag){
    if(pos>m){
        s[++num] = ans;
        c[num] = flag;
        return ;
    }
    DFS(ans,pos+1,flag);
    DFS(ans+(1<<pos-1),pos+3,flag+1);
}
 
int main(){
    while(cin>>n>>m>>ant){
        int p,q;
        for(int i=0;i<ant;i++){
            cin>>p>>q;
            a[p] += (1<<q-1);
        }
        memset(f,0,sizeof(f));
        num = 0;
        DFS(0,1,0);
      //  for(int i=1;i<=num;i++) cout<<s[i]<<" "<<c[i]<<endl;
        for(int i=1;i<3 && i<=n;i++){
            for(int j=1;j<=num;j++){ // When i==2, it means the current line, and when i==1, it means the current line 
                if(i==1){
                    if(a[i]&s[j]) continue;  // cannot be placed
                    f[i][s[j]]=c[j];
                }
                else {
                    if(a[i]&s[j]) continue;  // cannot be placed
                    for(int r=1;r<=num;r++){ // Cannot be placed and does not conflict with state 1, indicating the state of the previous line 
                    	if(a[i-1]&s[r]) continue;  // cannot be placed 
                    	if((s[j]&s[r])) continue;
                    	f[i][s[j]] = max(f[i][s[j]],f[i-1][s[r]]+c[j]); 
                    }
                }
            }
        }
        for(int i=3;i<=n;i++){
            for(int j=1;j<=num;j++){//current line 
            	if(s[j]&a[i]) continue;
                for(int r=1;r<=num;r++){//previous row i-1
                    if((s[r]&a[i-1]) || (s[j]&s[r])) continue;
                    for(int h=1;h<=num;h++){//one more line i-2
                        if((s[h]&a[i-3])||(s[j]&s[h])||(s[r]&s[h])) continue;
                        f[i][s[j]] = max(f[i][s[j]],f[i-2][s[h]]+c[j]+c[r]);
                    }
                }
            }
        }
        long long sum = 0;
        for(int i=1;i<=num;i++) 
        	sum = max(f[n][s[i]],sum);
       	cout<<sum<<endl;
    }
} 

/*
enter:
3 3 3
2 1
2 2
2 3
output: 2
*/

Topic 6:
Given a checkerboard of n∗m(1≤n, m≤11)n*m(1≤n, m≤11)n∗m(1≤n, m≤11), use 1∗21*21∗ 2 rectangles of dominoes cover this without overlapping
Checkerboard, find the number of plans covered.

#include<iostream>
#include<cstdio> 
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
using namespace std;
long long f[12][1<<14];
int s1[1<<14],s2[1<<14],s[1<<14],ss[1<<14];
int n,m,num,flag;
bool vist[1<<14];
 
void DFS(int ans1,int ans2,int pos){
    if(pos>n) {
        if(pos==n+1) {
            s1[++num] = ans1;
            s2[num] = ans2;
        }
        return ;
    }
    DFS(ans1,ans2,pos+1); // don't let go 
    DFS(ans1+(1<<pos-1)+(1<<pos),ans2,pos+2); // lay horizontally 
    DFS(ans1+(1<<pos-1),ans2+(1<<pos-1),pos+1); // vertical 
}
 
void dfs(int ans,int pos){
    if(pos>n){
        if(pos==n+1)
            s[++flag] = ans;
        return;
    }
    dfs(ans,pos+1);
    dfs(ans+(1<<pos-1)+(1<<pos),pos+2);
}
 
int main(){
    while(cin>>n>>m){
        if(n==0 && m==0) break;
        if(n%2 && m%2){ cout<<'0'<<endl; continue; }
        if(n > m) swap(n,m);
        if(n%2) swap(n,m);
        if(m==1) { cout<<'1'<<endl; continue; }
        num = 0; flag = 0;
        DFS(0,0,1);
        dfs(0,1); // First line all state search 
        memset(f,0,sizeof(f)); 
        for(int i=1;i<=flag;i++)
            f[1][s[i]] = 1;
       	int ant = (1<<n) - 1;
        for(int i=1;i<=num;i++){ //second line 
        	ss[i] = s1[i];
            for(int j=1;j<=flag;j++){ //first row 
                if((s2[i]&s[j])) continue;
                if((ant-s2[i])&(ant-s[j])) continue; //handle the same 0  
                f[2][s1[i]] += f[1][s[j]];
            }
        }
        sort(ss+1,ss+num);
        int ans = 0;
        ss[++ans] = ss[1];
        for(int i=2;i<=num;i++){  //Remove the same to avoid double counting 
            if(ss[i]!=ss[i-1]) ss[++ans] = ss[i];
        }
        for(int i=3;i<=m;i++){ //The third row
            for(int j=1;j<=num;j++){//State traversal of row i 
                for(int r=1;r<=ans;r++){ // Line i-1 ***** The same s1[r] can only be calculated once WA for a long time 
                    if(s2[j]&ss[r]) continue;
                    if((ant-s2[j])&(ant-ss[r])) continue;
                    f[i][s1[j]] += f[i-1][ss[r]];
                } 
            }
        } 
        cout<<f[m][(1<<n)-1]<<endl;
    }
}

Posted by santosj on Sat, 21 May 2022 19:44:58 +0300