Paint by Letters P-题解

· · 题解

Paint by Letters P-题解

题意

一个 n\times m 的矩形方阵，每一方格有一种目标颜色，颜色相同相邻的方格可以一起被染色，q 次询问，求出给且只给某一子矩形方阵染色需要染几次。

前置知识

欧拉平面图定理：K=|V|-|E|+R-1，K 为连通块个数，V 为点集，E 为边集，R 为区域数。

实现步骤

将可以一起染的连边，题目就是求联通块个数 K。

点和边的数量很好求，二维前缀和就能办到，瓶颈在求区域数 R。

我们先 bfs 找到整个图的独立区域，标记好每一个空格所在的区域编号，然后给每一个区域一个标记点（当然在区域内），如果现在的子图包含了这个标记点，我们就先暂时认为这个区域是存在于图中的。如果事实上它不存在，那唯一的情况是它的边缘在这个子图之外，导致这个区域成为了最外圈的无限区域的一部分，我们可以遍历矩形的边缘，查找部分在边缘内而部分在边缘外的区域，接着检验这个区域的标记点是否在矩形内，若是，将答案减一即可。

噫！好！我们过了！

代码

#include<bits/stdc++.h>

#define  Int  long long int
#define  Pub  public

using std::min;using std::max;

int n,m,q;
char p[1005][1005];
std::pair<int,int> s[1005][1005][5];

bool vis[1005][1005],siv[2000005];
int v[1005][1005],e1[1005][1005],e2[1005][1005],r[1005][1005];
int rid[1005][1005],cnt;
std::pair<int,int> t[1000005];
void dfs(int x,int y){
    if(x<0||x>n||y<0||y>m)return;
    if(vis[x][y])return;
    else vis[x][y]=1;
    if(s[x][y][3]==std::pair<int,int>{0,0})rid[x][y-1]=rid[x][y],dfs(x,y-1);
    if(s[x][y][4]==std::pair<int,int>{0,0})rid[x-1][y]=rid[x][y],dfs(x-1,y);
    if(s[x+1][y+1][1]==std::pair<int,int>{0,0})rid[x][y+1]=rid[x][y],dfs(x,y+1);
    if(s[x+1][y+1][2]==std::pair<int,int>{0,0})rid[x+1][y]=rid[x][y],dfs(x+1,y);
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)
        for(int j=(getchar(),1);j<=m;++j)
            p[i][j]=getchar();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            int vvv=1,ee1=0,ee2=0;
            if(p[i][j]==p[i-1][j])s[i][j][1]={i-1,j},++ee2;
            if(p[i][j]==p[i][j-1])s[i][j][2]={i,j-1},++ee1;
            if(p[i][j]==p[i+1][j])s[i][j][3]={i+1,j};
            if(p[i][j]==p[i][j+1])s[i][j][4]={i,j+1};
            v[i][j]=v[i-1][j]+v[i][j-1]-v[i-1][j-1]+vvv;
            e1[i][j]=e1[i-1][j]+e1[i][j-1]-e1[i-1][j-1]+ee1;
            e2[i][j]=e2[i-1][j]+e2[i][j-1]-e2[i-1][j-1]+ee2;         
        }
    }
    for(int i=0;i<=n;++i){
        for(int j=0;j<=m;++j){
            if(i==0&&j==0)r[i][j]=0;
            else if(i==0||j==0)r[i][j]=1;
            else r[i][j]+=r[i-1][j]+r[i][j-1]-r[i-1][j-1];
            if(vis[i][j])continue;
            else{
                ++cnt;
                rid[i][j]=cnt;
                t[cnt]=std::pair<int,int>{i,j};
                ++r[i][j];
                dfs(i,j);
            }
        }
    }

    while(~--q){
        memset(siv,0,sizeof(siv));
        int x_,y_,_x,_y;
        scanf("%d%d%d%d",&x_,&y_,&_x,&_y);
        int ans=0;
        ans+=v[_x][_y]+v[x_-1][y_-1]-v[x_-1][_y]-v[_x][y_-1];
        ans-=e1[_x][_y]+e1[x_-1][y_]-e1[x_-1][_y]-e1[_x][y_];
        ans-=e2[_x][_y]+e2[x_][y_-1]-e2[x_][_y]-e2[_x][y_-1];
        ans+=r[_x-1][_y-1]+r[x_-1][y_-1]-r[x_-1][_y-1]-r[_x-1][y_-1];
        for(int i=x_;i<_x;++i)
            if(s[i][y_][3]==std::pair<int,int>{0,0})
                if(t[rid[i][y_]].first>=x_&&t[rid[i][y_]].first<_x&&t[rid[i][y_]].second>=y_&&t[rid[i][y_]].second<_y&&!siv[rid[i][y_]])
                    siv[rid[i][y_]]=1,--ans;
        for(int i=y_;i<_y;++i)
            if(s[x_][i][4]==std::pair<int,int>{0,0})
                if(t[rid[x_][i]].first>=x_&&t[rid[x_][i]].first<_x&&t[rid[x_][i]].second>=y_&&t[rid[x_][i]].second<_y&&!siv[rid[x_][i]])
                    siv[rid[x_][i]]=1,--ans;
        for(int i=x_;i<_x;++i)
            if(s[i][_y][3]==std::pair<int,int>{0,0})
                if(t[rid[i][_y]].first>=x_&&t[rid[i][_y]].first<_x&&t[rid[i][_y]].second>=y_&&t[rid[i][_y]].second<_y&&!siv[rid[i][_y]])
                    siv[rid[i][_y]]=1,--ans;
        for(int i=y_;i<_y;++i)
            if(s[_x][i][4]==std::pair<int,int>{0,0})
                if(t[rid[_x][i]].first>=x_&&t[rid[_x][i]].first<_x&&t[rid[_x][i]].second>=y_&&t[rid[_x][i]].second<_y&&!siv[rid[_x][i]])
                    siv[rid[_x][i]]=1,--ans;
        printf("%d\n",ans);
    }

    return 0;
}