不要二

题目来源

牛客网：不要二

题目描述

二货小易有一个W*H的网格盒子，网格的行编号为0_{H-1，网格的列编号为0}W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。
对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为:
( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ) 的算术平方根
小易想知道最多可以放多少块蛋糕在网格盒子里。

输入描述

每组数组包含网格长宽W,H，用空格分割.(1 ≤ W、H ≤ 1000)

输出描述

输出一个最多可以放的蛋糕数

示例1

输入

3 2

输出

4

思路分析

解法一

• 坐标关系法
• 欧几里得距离不能为为2，说明横坐标或纵坐标的距离不能为2和0
• 用二维数组模拟网格，0表示可以放置蛋糕的，1表示不能放置的
• 数组初始值为0，从左下角开始遍历，找出不能放蛋糕的位置，注意数组的边界

解法二

• 找规律
• 这种方法较为复杂，需要根据条件确定每行能放置的蛋糕数目的规律，放置规律如图，当宽度和高度不同时，规律也不同，需要进行判断
  

代码展示

解法一

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

    //遍历二维数组，模拟坐标平面
    for (int i = 0; i < w; i++)
    {
        for (int j = 0; j < h; j++)
        {
            //0表放置了蛋糕，1表示没有
            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;
}

解法二

#include<iostream>
using namespace std;

//该函数用于统计每行的蛋糕数
int Count(int len)
{
	int count = len / 4 * 2;
	if (len % 4 >= 2)
	{
		//如果模4大于等于2，则除了前面整除的以外，还能再放置2个
		count += 2;
	}
	else if (len % 4 == 1)
	{
		//模4为1，除了整除的部分，还能再放一个
		count += 1;
	}
	return count;
}
int main()
{
	int W = 0;
	int H = 0;
	while (cin >> W >> H)
	{
		if (W * H < 4)
		{
			//方格只有一个
			if (W * H == 1)
			{
				cout << 1;
				continue;
			}
			//方格为1*3或者1*2
			else
			{
				cout << 2;
				continue;
			}
		}
		int sum = 0;
		//从第一行开始遍历
		for (int i = 0; i < H; i++)
		{
			//H代表方格纵高，W代表方格宽，从第一层开始遍历方格，统计每行能放的蛋糕数目
			//根据规律，一行放两个蛋糕就需要空两个位置，所以四个为一组
			//因为方格是长方形，所以每四行有两行是放的多的，另外两行是放的少的
			//可以根据行号模4的大小判断当前行是放的多的还是放的少的，多的直接调用Count函数，少的则用Count(W-2)
			if (i % 4 < 2)
			{
				sum += Count(W);
			}
			else {
				sum += Count(W - 2);//相当于空前两个位置，从第三个开始放蛋糕，所以-2
			}
		}
		cout << sum;
	}
	return 0;
}

总结

• 数组定义后未初始化则其元素值为随机值，定义后部分初始化，则未初始化的部分为0