AtCoder Beginner Contest竞赛题解 | 洛谷 AT_abc436_c 2x2 Placing

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：AtCoder Beginner Contest竞赛题解 | 汇总

【题目来源】

洛谷：[AT_abc436_c ABC436C] 2x2 Placing - 洛谷

【题目描述】

There is a grid with $ N $ rows and $ N $ columns. Let $ (i,j) $ denote the cell at the $ i $ -th row from the top and $ j $ -th column from the left. Initially, nothing is placed on the grid.
有一个N NN行N NN列的网格。用( i , j ) (i, j)(i,j)表示从上往下第i ii行、从左往右第j jj列的单元格。初始时，网格上未放置任何物品。

You will now perform $ M $ operations. The $ i $ -th operation $ (1\leq i\leq M) $ is as follows:
现在你将执行M MM次操作。第i ii次操作( 1 ≤ i ≤ M ) (1\leq i\leq M)(1≤i≤M)如下：

• Place a block that occupies a $ 2 \times 2 $ region with cell $ (R_i,C_i) $ as the top-left corner on the grid if and only if its position does not overlap with any other blocks already placed. More precisely, for the set of cells $ S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbrace $ , if there exists a block already placed on the grid that occupies any cell in $ S $ , do nothing; otherwise, place a block that occupies all four cells in $ S $ .
  当且仅当该位置与已放置的任何其他方块不重叠时，将一个占据2 × 2 2 \times 22×2区域且以单元格( R i , C i ) (R_i,C_i)(Ri​,Ci​)为左上角的方块放置在网格上。更准确地说，对于单元格集合S = { ( R i , C i ) , ( R i + 1 , C i ) , ( R i , C i + 1 ) , ( R i + 1 , C i + 1 ) } S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbraceS={(Ri​,Ci​),(Ri​+1,Ci​),(Ri​,Ci​+1),(Ri​+1,Ci​+1)}，若网格上已存在占据S SS中任一单元格的方块，则什么也不做；否则，放置一个占据S SS中全部四个单元格的方块。

After performing all operations, find how many blocks are placed on the grid.
在执行完所有操作后，求网格上放置的方块数量。

【输入】

The input is given from Standard Input in the following format:

$ N $ $ M $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ \vdots $ $ R_M $ $ C_M $

【输出】

Print the answer.

【输入样例】

4 3 1 1 2 2 2 3

【输出样例】

2

【算法标签】

《洛谷 AT_abc436_c 2x2 Placing》 #模拟#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;// 定义坐标对类型constintN=200005;// 最大点数（未使用）intn,m;// n: 坐标范围？, m: 操作次数intans;// 答案：不重叠的2×2正方形数量map<PII,int>mp;// 记录每个点是否被占用，1表示被占用intmain(){// 输入n和mcin>>n>>m;// 处理m次操作for(inti=1;i<=m;i++){intx,y;cin>>x>>y;// 输入2×2正方形的左上角坐标// 检查以(x,y)为左上角的2×2正方形是否与已存在的正方形重叠// 一个2×2正方形包含4个点：(x,y), (x,y+1), (x+1,y), (x+1,y+1)// 如果这4个点都没有被占用，说明可以放置新的正方形if(mp[{x,y}]!=1&&// 左上角mp[{x,y+1}]!=1&&// 右上角mp[{x+1,y}]!=1&&// 左下角mp[{x+1,y+1}]!=1)// 右下角{// 可以放置新正方形ans++;// 增加计数// 标记这4个点为已占用mp[{x,y}]=1;mp[{x,y+1}]=1;mp[{x+1,y}]=1;mp[{x+1,y+1}]=1;// 注意：这里没有检查坐标是否越界// 假设输入的坐标都在有效范围内}}// 输出不重叠的正方形数量cout<<ans<<endl;return0;}

【运行结果】

4 3 1 1 2 2 2 3 2