北京网站建设策划解决方案,防疫大数据平台,修水县城乡建设局网站,贵阳品牌网站建设公司题目解析#xff1a; 本题的重点是要读懂题意#xff0c;并且需要多读两遍#xff0c;才能读懂#xff0c;本题本质就是在二维数组中每个坐标去放蛋糕#xff0c; 一个坐标位置放了蛋糕#xff0c;跟他欧几里得距离为2的位置不能放蛋糕#xff0c;这个就是关键点。对于两…题目解析 本题的重点是要读懂题意并且需要多读两遍才能读懂本题本质就是在二维数组中每个坐标去放蛋糕 一个坐标位置放了蛋糕跟他欧几里得距离为2的位置不能放蛋糕这个就是关键点。对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为: ( (x1-x2) * (x1-x2) (y1-y2) * (y1-y2) ) 的算术平方根 。 也就是说如果(x1,y1)放了蛋糕则满足 ( (x1-x2) * (x1-x2) (y1-y2) * (y1-y2) ) 4的(x2,y2)不能放蛋糕。 ( (x1-x2) * (x1-x2) (y1-y2) * (y1-y2) ) 4看起来是一个无解的表达式。但是可以进行加法表达式分解134 314 224 044 404但是前三个表达式是不可能的因为(x1-x2) * (x1-x2)表达式结果不能等于2或3。那么也就是说( (x1-x2) * (x1-x2) 和(y1-y2) * (y1-y2) )两个表达式一个等于0一个等于4。可以看出假设放蛋糕的位置是(x1,y1)则不能放蛋糕的位置(x2,y2)满足x1x2,y1-y22或者x1-x22,y1y2。 解题思路 将题目像上面那样一剖析看似复杂的一个题就变得很简单了只需要一个二维数组buff先将数组的每一个元素初始化为1表示可以放蛋糕如果buff[i][j]可以放蛋糕先将计数器然后将buff[i][j2]和buff[i2][j]处标记为不能存放蛋糕即为0。 图解思路
#include vector
#include iostream
using namespace std;int main()
{int w,h,ret 0;cin w h;vectorvectorint buff;buff.resize(w);for(auto e:buff)e.resize(h, 1);for(int i 0; i w; i){for(int j 0; j h; j){if(buff[i][j] 1){ret;if((i2) w)buff[i2][j] 0;if((j2) h)buff[i][j2] 0;}}}cout ret endl;return 0;
}
