算法1

usaco,好题打卡

欧拉定理

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1010;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
PII rep[N][N];
bool vis[N][N];
char g[N][N];
int n, m, q;
int es[N][N], cs[N][N];
int star[N][N];
int area[N][N], cnt;
int f[N][N], sf[N][N];
bool del[N][N];

bool check_con(int x1, int y1, int x2, int y2)
{
    if(x1 == x2)
    {
        if(y1 > y2) swap(y1, y2);
        return g[x2][y2] != g[x2 + 1][y2];
    }
    else if(y1 == y2)
    {
        if(x1 > x2) swap(x1, x2);
        return g[x2][y2] != g[x2][y2 + 1];
    }
}

void dfs(int x, int y, int repx, int repy)
{
    vis[x][y] = true;
    rep[x][y] = {repx, repy};
    for(int u = 0; u < 4; ++ u)
    {
        int ux = x + dx[u], uy = y + dy[u];
        if(ux < 0 || uy < 0 || ux > n || uy > m) continue;
        if(vis[ux][uy]) continue;
        if(check_con(x, y, ux, uy))
            dfs(ux, uy, repx, repy);
    }
}

bool check_inc(int x1, int y1, int x2, int y2, int x, int y)
{
    return (x >= x1) && (x <= x2) && (y >= y1) && (y <= y2);
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; ++ i)
        scanf("%s", g[i] + 1);
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
        {
            es[i][j] = es[i - 1][j] + es[i][j - 1] - es[i - 1][j - 1];
            if(g[i][j] == g[i][j - 1]) es[i][j] ++;
            if(g[i][j] == g[i - 1][j]) es[i][j] ++;
        }
    for(int i = 0; i <= n; ++ i)
        for(int j = 0; j <= m; ++ j)
            if(!vis[i][j])
            {
                f[i][j] = 1;
                dfs(i, j, i, j);
            }
    for(int i = 0; i <= n; ++ i)
        for(int j = 0; j <= m; ++ j)
        {
            if(!i && !j) continue;
            else if(!i) sf[i][j] = sf[i][j - 1] + f[i][j];
            else if(!j) sf[i][j] = sf[i - 1][j] + f[i][j];
            else sf[i][j] = sf[i - 1][j] + sf[i][j - 1] - sf[i - 1][j - 1] + f[i][j];
        }
    while(q --)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        int V = (x2 - x1 + 1) * (y2 - y1 + 1);
        int E = es[x2][y2] - es[x2][y1 - 1] - es[x1 - 1][y2] + es[x1 - 1][y1 - 1];
        int F = sf[x2][y2] - sf[x2][y1 - 1] - sf[x1 - 1][y2] + sf[x1 - 1][y1 - 1];
        vector<PII> pos;
        for(int i = y1; i <= y2; ++ i)
        {
            int repx = rep[x1 - 1][i].x, repy = rep[x1 - 1][i].y;
            if(check_inc(x1, y1, x2, y2, repx, repy) && !del[repx][repy])
            {
                F --;
                del[repx][repy] = true;
                pos.push_back({repx, repy});
            }
        }
        for(int i = y1; i <= y2; ++ i)
        {
            int repx = rep[x2][i].x, repy = rep[x2][i].y;
            if(check_inc(x1, y1, x2, y2, repx, repy) && !del[repx][repy])
            {
                F --;
                del[repx][repy] = true;
                pos.push_back({repx, repy});
            }
        }
        for(int i = x1; i <= x2; ++ i)
        {
            int repx = rep[i][y1 - 1].x, repy = rep[i][y1 - 1].y;
            if(check_inc(x1, y1, x2, y2, repx, repy) && !del[repx][repy])
            {
                F --;
                del[repx][repy] = true;
                pos.push_back({repx, repy});
            }
        }
        for(int i = x1; i <= x2; ++ i)
        {
            int repx = rep[i][y2].x, repy = rep[i][y2].y;
            if(check_inc(x1, y1, x2, y2, repx, repy) && !del[repx][repy])
            {
                F --;
                del[repx][repy] = true;
                pos.push_back({repx, repy});
            }
        }
        for(int i = x1; i <= x2; ++ i)
            if(g[i][y1 - 1] == g[i][y1]) E --;
        for(int i = y1; i <= y2; ++ i)
            if(g[x1 - 1][i] == g[x1][i]) E --;
        F ++;
        for(auto &p: pos) del[p.x][p.y] = false;
        printf("%d\n", F + V - E - 1);
    }
    return 0;
}