Mondrian’s dream:
Mondrian’s dream under pressure from DP:
To find the number of plans, first of all, because there are only two ways to place them, and they have to be filled up, it is actually the same as the dyeing problem (black and white). For a certain plan, once the horizontal placement is determined, then the remaining The only solution is to put it vertically. It is worth noting that when enumerating horizontal placement, we must find a way to ensure that the remaining space is legal for vertical placement.
When we enumerate the situation of horizontal placement, we use the binary number (state j) for the i-th column to indicate whether a horizontal chess piece will be placed in each position. In order to avoid confusion, we use each column and each row. When placing them horizontally, choose to align the leftmost end of the chess piece with the leftmost end of the column. Then, after each chess piece is placed horizontally, it will inevitably poke out one square to the adjacent column on the right.
So we have two boundary conditions:
1.f[[0][0]=1; Do not place any horizontal ones in column 0, because we only need to fill columns 1~m. Obviously, this is the only legal way to place column 0;
2.f[m][0]; is the final answer, because if you enumerate to the last column, if you put another horizontal one, it will poke out the right border, so you can’t put another horizontal one in the last column. . This is very similar to the puzzling switch in the previous algorithm competition advanced guide. After the previous m-1 column situation is processed, the m-th column is actually uniquely determined.
State transition: f[i,j] + =f[i-1,k] is actually easy to understand, because f[i,j] represents the number of legal options when the i-th column is placed in state j, then he In fact, it is equal to the sum of all the previous placement methods that conflict with state j.
The key is to ensure there is no conflict, two points:
1. Not heavy. For the i-1th column, assuming that the p-th row has let go of the horizontal position, then the p-th position of k is 1; now the i-th column must also be horizontal in the p-th row, and then the p-th position of j is also 1 .So, it is obvious that a position is covered repeatedly, which is illegal. So we have to satisfy j & amp; & amp;k==0 between the current state j and the state k in the previous column to be legal, and then we can carry out state transfer;
2. No leaks. After we put all the horizontal chess pieces in the columns that satisfy 1., any 1X1 small grid in the current column, i.e., the i-th column, must be in one of three states: being horizontal by the previous column. Covered by chess, covered by the current row of horizontal chess, and empty. Then of course the vacant positions will not be covered by the following columns, but need to be covered by the vertical chess pieces, so each vacant position must exist in consecutive pairs, that is, there cannot be an odd number of consecutive 0s in i || k. The range of i || k is limited, we can preprocess in advance whether the status of all i || k is legal st[i || k].
Therefore, each time all the j rows of the current column and k rows of the previous column are enumerated, the transfer f[i][j] + =f[i-1][k].
#include <iostream>
#include <cstring>
using namespace std;
const int N = 12, M = 1<< N;
long long f[N][M] ;//The first dimension represents the column, the second dimension represents the row, and the number of solutions is stored
bool st[M]; //Storage whether each state has an odd number of consecutive 0s. If there are an odd number of 0s, it is an invalid state. If there are an even number of zeros, it is set to true.
int m, n;
int main()
{
//Part 1: Preprocessing 1. Remove illegal methods
while (cin >> n >> m, n || m) //Read n and m, and continue reading if they are not two 0s, which is a legal input.
{
memset(f,0,sizeof f);//Initialization
for(int i = 0; i < (1 << n); i + + ) //First preprocess that each column cannot have an odd number of consecutive 0s
{
st[i]=true;//Assuming it is true, if the state does not have an odd number of consecutive 0s, it will be marked as true
int cnt = 0;//Record the number of consecutive 0s in the current paragraph
for(int j = 0; j < n; j + + ) //Traverse this column, from top to bottom
{
if ( (i >> j) & amp; 1) //If this row of this column is 1
{
//i >> j-bit operation, representing the j-th bit of the binary number of i (i is a state here);
// & amp;1 is used to determine whether the bit is 1. If it is 1, enter if
if (cnt & 1)//Look at the number of consecutive 0s in the row above the column. If it is an odd number (cnt &1 is true), the state is illegal.
st[i]=false;
cnt = 0; // Since this bit is 1, the counter is cleared.
}
else cnt + + ; // Otherwise, if the bit is still 0, count the counter of consecutive 0s + + .
}
if (cnt & 1) //The bottom line of the column determines the number of consecutive 0s. If it is an odd number (cnt &1 is true), the state is illegal.
st[i]=false;
}
f[0][0]=1;//The 0th column cannot be pushed from the front, and only 1~m columns need to be filled, so there is only one situation: put it vertically
//Part 2: Preprocessing 2
// After the continuous 0 judgment of each state above, some states have been filtered out.
// Let’s look at further judgment: look at the two situations where the i-2th column extends over and the i-1th column extends over:
//Because column i-2 will extend over column i-1, column i-1 cannot extend out.
for(int i=1;i<=m;i + + )
{
for (int j = 0; j < (1 << n); j + + ) //Enumerate all row states of column i
{
for (int k = 0; k < (1 << n); k + + )//Enumerate all row statuses in column i-1
{
//Then determine whether the 1 position in the i-th column conflicts with the i-1 column
if ((j & amp; k ) == 0 & amp; & amp; st[ j | k])
//f[i][j]: The total number of 1's in column i-1
//Source two parts:
//f[i-1][k] indicates the number of 1's inserted into column i-1 in column i-2, and the 1 passively generated in column i-1
//f[i][j] indicates the number of 1s inserted into column i in column i-1, which is the 1 actively generated in column i-1
f[i][j] + =f[i-1][k];
}
}
}
//The above for loop i starts from 1 and ends with m, but i-1 is used, so in fact f[i][] starts from 0, the last column is m-1, and the m column is to determine whether there is m -1 column sticking out
//f[m][0] represents the number of all solutions after the first m-1 columns have been processed and the m-1th column has not been extended.
//That is, the number of solutions that have been processed on the entire chessboard
printf("%lld\
",f[m][0]);
}
return 0;
}
Shortest Hamilton path:
Assumption: There are seven points in total, represented by 0, 1, 2, 3, 4, 5, 6. Then assume that the end point is 5. Here we also assume that we have not reached the point 5 yet, and go The end point reached is 4, then there are the following six situations:
first: 0–>1–>2–>3–>4 distance: 21
second: 0–>1–>3–>2–>4 distance: 23
third: 0–>2–>1–>3–>4 distance: 17
fourth: 0–>2–>3–>1–>4 distance: 20
fifth: 0–>3–>1–>2–>4 distance: 15
sixth: 0–>3–>2–>1–>4 Distance: 18
If you were a businessman at this time, what path would you take? Obviously, you would take the fifth situation, right? Because the end point of each journey is 4, and the available points for each plan are 0 ~4, and what the businessman is looking for is the shortest distance to the point 5, and there is only one way to go from 4 to 5, so we choose the fifth option, which can find the shortest distance before reaching the point 5, and the end point is The shortest distance of the plan of 4. At this time, the shortest distance from 0 to 5 is (15 + the distance from 4 to 5). (Assume 4–>5=8)
Similarly: Suppose we have not reached the point of 5, and the end point is 3, then there are six situations:
first: 0–>1–>2–>4–>3 distance: 27
second: 0–>1–>4–>2–>3 distance: 22
third: 0–>2–>1–>4–>3 distance: 19
fourth: 0–>2–>4–>1–>3 distance: 24
fifth: 0–>4–>1–>2–>3 distance: 26
sixth: 0–>4–>2–>1–>3 Distance: 17
At this point we can make a decisive decision: go for the sixth option!!!, and the shortest distance from 0 to 5 at this time is (17 + the distance from 3 to 5) (assuming 3–>5=5 )
After the above two categories of situations, we can conclude that when reaching 5:
1. The shortest distance with 4 as the end point is: 15 + 8 = 23;
2. The shortest distance with 3 as the end point is: 17 + 5 = 22;
After careful consideration, the businessman decided to take the shortest distance ending at 3. At this time, the shortest distance was updated to: 22.
Of course, by analogy, there will also be situations where 1 is the end point and 2 is the end point. At this time, we can perform the above operations to continuously update the shortest distance to the point 5, and finally get the shortest distance to the point 5. distance, and then return to the original hypothesis, and then assume that 1, 2, 3, and 4 are the end points, and finally continue to update, and finally we can get the answer we want
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20,M=1<<N;
int f[M][N];//M represents a binary number, used to represent the path status of 0~j: 1011 represents the three points of 0, 1, and 3 (looking from the right), N represents the final destination some point
int w[N][N];//w represents an undirected graph, the distance between two points
int main()
{
int n;
scanf("%d", & amp;n);
for(int i=0;i<n;i + + )//Input undirected graph
for(int j=0;j<n;j + + )
scanf("%d", & amp;w[i][j]);
memset(f,0x3f3f3f3f,sizeof(f));//Because the minimum value is required, it is initialized to infinity
f[1][0]=0; //Because zero is the starting point, the only distance from 0 to 0 is: f[1][0]=0;
for(int i=0;i<(1<<n);i + + )//i is a binary number, used to represent the path status of 0~j: 1011 means taking the three points 0, 1, and 3 (Looking from the right)
for(int j=0;j<n;j + + )//j indicates which point to go to
if((i>>j) & amp;1)//In the path of i, 0~j, see if the bit is 1, then the j bit of i must be 1.
for(int k=0;k<n;k + + )//k represents the shortest distance before point j, with k as the end point
if((i>>k) & amp;1)//The path of i represents the path from 0 to k. See if this bit is 1, then the k bit of i must be 1.
//i-(1<<j) indicates whether the distance to k from a certain point + k~j in path i is shorter
f[i][j]=min(f[i][j],f[i-(1<<j)][k] + w[k][j]);//Update the shortest distance
//The for above is i<(1<<n), so -1 is needed here. If i starts from 1, it is i<=(1<<n), and -1 is not used here.
printf("%d\
",f[(1<<n)-1][n-1]);//Indicates that all points have been traveled and the end point is the shortest distance of n-1
return 0;
}