题解：AT_abc436_c [ABC436C] 2x2 Placing

· · 题解

思路

本题主要是模拟 2\times2 区域的放置过程，逻辑如下：

放置条件：以输入的坐标 (x, y) 为左上角的 2\times2 区域，其四个顶点 (x,y)、(x,y+1)、(x+1,y)、(x+1,y+1) 必须均未被占用。

状态记录：使用哈希映射记录网格中每个位置的占用状态，实现快速的查询与标记。

流程处理：遍历每个输入的坐标，若满足放置条件，则标记该 2\times2 区域的四个格子为已占用，并将成功放置的数量加1。

代码

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
#define fir first
#define sec second
#define mk make_pair
#define pii pair<int,int>
#define pb push_back
#define pf push_front
#define pq priority_queue
#define max(a,b) (a>b ? a : b )
#define min(a,b) (a<b ? a : b )
#define abs(x) (x<0 ? -x : x)
#define ccmap __gnu_pbds::cc_hash_table 
#define gpmap __gnu_pbds::gp_hash_table

/*-------------------------------------------------------------------------------------------*/

const int dx[]= {0,0,1,1};
const int dy[]= {0,1,0,1};//偏移量（自己，下边，右边，右下角） 
int n,m;
int x,y;
map<pii,bool> mp; //使用哈希表来记录 
int ans;

bool check() { // 检查以(x,y)为左上角的2×2正方形是否可放置
    for (int j=0; j<4; j++) {
        int nx=x+dx[j],ny=y+dy[j];
        if (mp[mk(nx,ny)]) {
            return false;
        }
    }
    return true;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for (int i=1; i<=m; i++) {
        cin>>x>>y;
        if (check()) {
            for (int j=0; j<4; j++) {
                int nx=x+dx[j],ny=y+dy[j];
                mp[mk(nx,ny)]=true; //标记 
            }
//          cout<<"    "<<x<<' '<<y<<endl; 
            ans++;
        }
    }
    cout<<ans;
    return 0;
}