模拟试题2 - 二货小易的网格盒子

题目描述

二货小易有一个W*H的网格盒子，网格的行编号为0H-1，网格的列编号为0W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。

对于两个格子坐标(x1,y1), (x2,y2)的欧几里得距离为：((x1-x2)(x1-x2)+(y1-y2)(y1-y2))的算术平方根。

小易想知道最多可以放多少块蛋糕在网格盒子里。

输入描述

每组数组包含网格长宽W,H，用空格分隔。(1<=W、H<=1000)

输出描述

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

输入例子

3 2

输出例子

4

题目解析

根据题意，可以推测出蛋糕数最多的放置方案：将网格进行分区，每四个构成一个正方形的网格作为一个分区，类似于坐标变换。假设原坐标为(x,y),那么变换后的分区坐标为(x/2,y/2)。当变换后的分区坐标满足横纵坐标之和为偶数时，该分区内的4个网格均可放置蛋糕。

解题程序

#include <iostream>
using namespace std;

int main()
{

  int W,H;
  int cnt=0; // 定义可放的蛋糕数
  cin>>W>>H; // 输入盒子网格的行列数

  for(int i = 0; i<H; i++)
      for(int j = 0; j < W; j++)
        if((i/2 + j/2) % 2 == 0)
          cnt++;
  cout<<cnt<<endl;
  return 0;
}