[day_060423] no two

No two

Title source

Cattle from ： No two

Title Description

Er Huo Xiaoyi has one W*H Grid box , The row number of the grid is 0_{H-1, The column number of the grid is 0}W-1. At most one cake can be placed in each grid , The Euclidean distance between any two cakes cannot be equal to 2.
For two lattice coordinates (x1,y1),(x2,y2) Euclidean distance of :
( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ) The arithmetic square root of
Xiao Yi wants to know how many cakes can be put in the grid box at most .

Input description

Each array contains the length and width of the grid W,H, Split with spaces .(1 ≤ W、H ≤ 1000)

Output description

Output a maximum number of cakes

Example 1

Input

3 2

Output

4

Thought analysis

Solution 1

• Coordinate relation method
• Euclidean distance cannot be 2, Explain that the distance between abscissa or ordinate cannot be 2 and 0
• Use a two-dimensional array to simulate the mesh ,0 It means that the cake can be placed ,1 Indicates that cannot be placed
• The initial value of the array is 0, Start from the lower left corner and traverse , Find out where you can't put the cake , Notice the bounds of the array

Solution 2

• Looking for a regular
• This method is more complicated , It is necessary to determine the rule of the number of cakes that can be placed in each row according to the conditions , The placement pattern is shown in the figure , When the width and height are different , The rules are also different , It needs to be judged
  

Code display

Solution 1

#include<iostream>
using namespace std;
int main()
{
    
    int w, h = 0;
    int count = 0;
    cin >> w >> h;
    int a[1000][1000] = {
     0 };

    // Traversing a two-dimensional array , Simulate coordinate plane 
    for (int i = 0; i < w; i++)
    {
    
        for (int j = 0; j < h; j++)
        {
    
            //0 The table placed the cake ,1 It means that there is no 
            if (a[i][j] == 0)
            {
    
                count++;
                if (i < w - 2)
                {
    
                    a[i + 2][j] = 1;
                }
                if (j < h - 2)
                {
    
                    a[i][j + 2] = 1;
                }
            }
        }
    }
    cout << count;
    return 0;
}

Solution 2

#include<iostream>
using namespace std;

// This function is used to count the number of cakes in each row 
int Count(int len)
{
    
	int count = len / 4 * 2;
	if (len % 4 >= 2)
	{
    
		// If module 4 Greater than or equal to 2, Then in addition to the previous division , It can also be placed 2 individual 
		count += 2;
	}
	else if (len % 4 == 1)
	{
    
		// model 4 by 1, Except for the divisible part , You can put another 
		count += 1;
	}
	return count;
}
int main()
{
    
	int W = 0;
	int H = 0;
	while (cin >> W >> H)
	{
    
		if (W * H < 4)
		{
    
			// There is only one square 
			if (W * H == 1)
			{
    
				cout << 1;
				continue;
			}
			// The square is 1*3 perhaps 1*2
			else
			{
    
				cout << 2;
				continue;
			}
		}
		int sum = 0;
		// Go through... From the first line 
		for (int i = 0; i < H; i++)
		{
    
			//H Represents the vertical height of the square ,W Represents square width , Traverse the grid from the first layer , Count the number of cakes that can be placed in each row 
			// According to the law , Two cakes in a row need two empty positions , So four in a group 
			// Because the square is rectangular , So there are two lines in every four lines , The other two lines are put less 
			// It can be modeled according to the line number 4 The size of determines whether the current line is put more or less , Many direct calls Count function , Use less Count(W-2)
			if (i % 4 < 2)
			{
    
				sum += Count(W);
			}
			else {
    
				sum += Count(W - 2);// Equivalent to two unprecedented positions , Put the cake from the third , therefore -2
			}
		}
		cout << sum;
	}
	return 0;
}

summary

• If the array is not initialized after definition, its element value is a random value , Partial initialization after definition , Then the uninitialized part is 0