2.1.3 TileBoard
TileBoard is an algorithm that divides the plane by dividing and conquering. It attaches L-shaped tiles to the plane of a N*N lattice. It pays attention to the power of N to 2. There is one vacant basic square which need not be pasted. L-shaped tiles are composed of three basic squares.
Why can we divide and conquer this problem? Assuming N=8, there are 64 basic squares. If you paste L-shaped tiles randomly, you will find that the last three basic squares are not connected, which is actually the principle of jigsaw puzzle. Then a way of mapping, let the final plane covered with L-shaped tiles, in addition to the vacancy of the basic grid. This also coincides with the mathematical principle of 3m+1=N*N, that is, N is the power of 2.
The mathematical theory of divide-and-conquer method is essentially the inverse proof of induction: divide-and-conquer method - from big to small; induction method - from small to big.
- For basic problems, when n==2, it is a plane with four basic squares. Obviously, a L-shaped tile can be pasted directly.
- When n=2k, if it can be decomposed into t=n/4 planes with four basic squares, it is proved that 16 basic squares can be decomposed into four planes with the same size and four basic squares from the middle axis, while 64 basic squares can be divided into four planes with 16 basic squares, by the same analogy; and 2k*2k=4k basic squares, so eventually it will be. Planes with 4k-1 and 4 basic squares.
- If n=2k holds, i.e. (n*n)/4==22k-2 small planes, then when n=2k+1, it contains 22K small planes, which can be divided into four basic squares. Why is that proven? Because the premise is a small square with power of 2, if it is 4*5 small squares, it can not be divided into four planes with the same size of basic squares. And 22k-2 and 22K are powers of 4, which can be divided, so the argument is valid.
How do you implement the above idea in code?
In fact, according to whether the divisions are based on the results of the divisions, the quick sorting is carried out. The divisions are divided according to the results of the divisions, so the divisions are divided first, then the divisions are divided; and the merger sorting is to divide the large number into a small number first, and then to govern it. So divide and treat first. TileBoard calls the function of recursive score according to the result of rule, so it is first treated and then divided. (Note: It is not based on whether the recursive function program is placed in front or behind of the rule to decide whether to divide and conquer first or divide and conquer first, because the dividing function can actually be placed in front or behind, according to the conditions of judging the termination of recursion such as if, the dividing and conquering relationship can be the same; it is based on the dividing and conquering relationship. The basis is determined by the results of governance.
Then, a basic framework of divide-and-conquer law can be realized first.
//tile problem
void DivideMerge::Tile(int sum, Point point, Point position)
{
//Basic recursive framework, that is, when what conditions are satisfied, continue to call the function, where the function is not limited, a quarter, all coordinates are the coordinates of the lower right corner.
//point.setTile(true);
if (sqrt(sum) >2)
{
int len = sqrt(sum);
int t = len / 2;
Point leftUpPosition, leftDownPosition, rightUpPosition, rightDownPosition;
Point centerPoint;
centerPoint.setX(position.getX() - t);
centerPoint.setY(position.getY() - t);
leftUpPosition.setX(position.getX() - t);
leftUpPosition.setY(position.getY() - t);
leftDownPosition.setX(position.getX());
leftDownPosition.setY(position.getY()-t);
rightUpPosition.setX(position.getX()-t);
rightUpPosition.setY(position.getY());
rightDownPosition.setX(position.getX());
rightDownPosition.setY(position.getY());
//****************************************************************
Point leftUpPoint, leftDownPoint, rightUpPoint, rightDownPoint; //This is an empty point or a tile d point.
//By directly calculating the position coordinates of these points and changing their tile s to true, the original empty space can be regarded as true???
//point is a vacant or filled position
//point is the current vacancy. Note that when the cursor widens, press insert to restore it.
int quadrant; //Quadrants are used to represent the position of empty defects and filling points, respectively.
if (point.getX() <= centerPoint.getX() )
{
if (point.getY() <= centerPoint.getY())
{
quadrant = 2; //Vacancies in the second quadrant
}
else
{
quadrant = 1;
}
}
else
{
if (point.getY() <= centerPoint.getY())
{
quadrant = 3; //Vacancies in the second quadrant
}
else
{
quadrant = 4;
}
}
switch (quadrant)
{
case 1:{
//Explain point in the first quadrant
rightUpPoint = point;
leftUpPoint.setTile(true);
leftUpPoint.setX(centerPoint.getX());
leftUpPoint.setY(centerPoint.getY());
leftDownPoint.setTile(true); //third quadrant
leftDownPoint.setX(centerPoint.getX()+1);
leftDownPoint.setY(centerPoint.getY());
rightDownPoint.setTile(true);
rightDownPoint.setX(centerPoint.getX() + 1); //Delta Quadrant
rightDownPoint.setY(centerPoint.getY() + 1);
}break;
case 2:{
//Explain point in the second quadrant
leftUpPoint = point;
leftDownPoint.setTile(true); //third quadrant
leftDownPoint.setX(centerPoint.getX()+1);
leftDownPoint.setY(centerPoint.getY());
rightUpPoint.setTile(true); //First quadrant
rightUpPoint.setX(centerPoint.getX());
rightUpPoint.setY(centerPoint.getY()+1);
rightDownPoint.setTile(true);
rightDownPoint.setX(centerPoint.getX() + 1); //Delta Quadrant
rightDownPoint.setY(centerPoint.getY() + 1);
}break;
case 3:{
leftDownPoint = point;
leftUpPoint.setTile(true);
leftUpPoint.setX(centerPoint.getX());
leftUpPoint.setY(centerPoint.getY());
rightUpPoint.setTile(true); //First quadrant
rightUpPoint.setX(centerPoint.getX());
rightUpPoint.setY(centerPoint.getY()+1);
rightDownPoint.setTile(true);
rightDownPoint.setX(centerPoint.getX() + 1); //Delta Quadrant
rightDownPoint.setY(centerPoint.getY() + 1);
}break;
case 4:{
rightDownPoint = point;
leftUpPoint.setTile(true);
leftUpPoint.setX(centerPoint.getX());
leftUpPoint.setY(centerPoint.getY());
leftDownPoint.setTile(true);
leftDownPoint.setX(centerPoint.getX() + 1); //Third Quadrant
leftDownPoint.setY(centerPoint.getY());
rightUpPoint.setTile(true); //First quadrant
rightUpPoint.setX(centerPoint.getX());
rightUpPoint.setY(centerPoint.getY() + 1);
}break;
}
Tile(sum / 4, leftUpPoint, leftUpPosition); //Left upper
Tile(sum / 4, leftDownPoint, leftDownPosition); //Left lower
Tile(sum / 4, rightUpPoint, rightUpPosition); //Right upper
Tile(sum / 4, rightDownPoint, rightDownPosition); //lower right
}
else if(sqrt(sum)==2) //if(sqrt(n)==2), indicating that there is only one location where tile s can exist
{
//Direct tiles of points that are not tiled
//The position must be in the lower right corner, while the point is empty or filled.
//Fill in all the remaining four
quardPoint[point.getX()][point.getY()] = point;
}//else if
}
Summary: The implementation of Tile algorithm is mainly to store the basic grid. In the program, point class is used to store the basic grid, which contains the coordinates and markers of X and y, that is, the markers have been pasted with the true square position of L-shaped ceramic tile. Where x and Y correspond to the subscript of the array.
If the vacancy or the patched small squares are in the upper left plane of the four planes that have been divided, then an L-shaped tile is affixed to the small squares adjacent to the lower right corner of the upper left plane in the remaining three planes, setting the markers of the point s of the three small squares around them to true.
The arithmetic logic of the program is not difficult. It mainly stores the data, disposes the data well and makes the arithmetic self-contained.
The following is the main tone function:
vector<vector<Point>> DivideMerge::TileBoard(int n, int m, Point point) //point is an initial empty defect
{
//You can initialize it with a point value
quardPoint.resize(n+1);
for (int i = 0; i <= n; i++)
{
quardPoint[i].resize(m+1);
}
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
quardPoint[i][j] = *new Point();
quardPoint[i][j].setTile(false);
quardPoint[i][j].setX(i);
quardPoint[i][j].setY(j);
}
}
Point position;
position.setX(n);
position.setY(m); //Vertex coordinates in the lower right corner
int sum = n*m;
Tile(sum, point, position); //Call the recursive function Tile(int n, Point point, Point position)
quardPoint[point.getX()][point.getY()].setTile(false);
return quardPoint;
}