算法1

贪心+dfs

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second
const int N = 2010, INF = 0x3f3f3f3f;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool st[N][N];
int n;
int cnt;

PII check(int x, int y)
{
    int res = 0;
    for(int u = 0; u < 4; ++ u)
    {
        int ux = x + dx[u], uy = y + dy[u];
        if(st[ux][uy])
            res ++;
    }
    if(res == 3)
    {
        for(int u = 0; u < 4; ++ u)
        {
            int ux = x + dx[u], uy = y + dy[u];
            if(!st[ux][uy])
                return {ux, uy};
        }
    }
    return {INF, INF};
}

void dfs(int x, int y)
{
    PII ck = check(x, y);
    if(ck.x != INF)
    {
        cnt ++;
        st[ck.x][ck.y] = true;
        dfs(ck.x, ck.y);
    }
    for(int u = 0; u < 4; ++ u)
    {
        int ux = x + dx[u], uy = y + dy[u];
        if(st[ux][uy])
        {
            PII r = check(ux, uy);
            if(r.x != INF)
            {
                st[r.x][r.y] = true;
                cnt ++;
                dfs(r.x, r.y);
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x += 500, y += 500;
        if(st[x][y]) cnt --;
        else 
        {
            st[x][y] = true;
            dfs(x, y);
        }
        printf("%d\n", cnt);
    }

    return 0;
}