题解 P1524 【十字绣】

· · 题解

分析

一开始以为是一道DP题，后来发现状态不太好转移

后来看了题解才发现竟然是一道图论+dfs，确实不太好想

我们把格子上的点抽象成图中的节点，同时开一个数组记录它的入度

如果该点与正面的某一条线相连，我们就把它的入度加1

如果该点与反面的某一条线相连，我们就把它的入度减1

那么这一个点所需要的线的数量就是它的入度的绝对值

我们来举一个例子，如果一个点连着3个正面的线，又连着2个反面的线

那么2个正面的线就会和2个反面的线抵消，也就是转了一圈

而剩下的那一个正面的线必须另用一针

这样，对于每一个联通块，我们统计该联通块内所有节点的入度之和，最后把它除以二

因为一条线的起点和终点我们分别算了一遍

有一种特殊情况就是该联通块所有节点的入度之和为0 这说明一条线就可以解决，要特判一下

最后要注意字符\在判断的时候要写成\\，或者用它的ASCII值92，否则会报错

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,maxk=205;
int head[maxn],tot=1,du[maxn],cnt,a[maxk][maxk],bb[maxn],ans,vis[maxn];
struct asd{
    int from,to,next;
}b[maxn];
void ad(int aa,int bb,int cc){
    b[tot].from=aa;
    b[tot].to=bb;
    b[tot].next=head[aa];
    head[aa]=tot++;
    if(cc==0) du[aa]++;
    else du[aa]--;
}
char s[maxk][maxk];
void dfs(int now){
    ans+=abs(du[now]);
    vis[now]=1;
    for(int i=head[now];i!=-1;i=b[i].next){
        int u=b[i].to;
        if(vis[u]==0){
            dfs(u);
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+2;i++){
        for(int j=1;j<=m+2;j++){
            a[i][j]=++cnt;
        }
    }
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++){
            if(s[i][j]=='\\'){
                ad(a[i][j],a[i+1][j+1],0);
                ad(a[i+1][j+1],a[i][j],0);
                bb[a[i][j]]=bb[a[i+1][j+1]]=1;
            }
            if(s[i][j]=='/'){
                ad(a[i][j+1],a[i+1][j],0);
                ad(a[i+1][j],a[i][j+1],0);
                bb[a[i][j+1]]=bb[a[i+1][j]]=1;
            }
            if(s[i][j]=='X'){
                ad(a[i][j+1],a[i+1][j],0);
                ad(a[i][j],a[i+1][j+1],0);
                ad(a[i+1][j],a[i][j+1],0);
                ad(a[i+1][j+1],a[i][j],0);
                bb[a[i][j]]=bb[a[i+1][j]]=bb[a[i+1][j+1]]=bb[a[i][j+1]]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        for(int j=1;j<=m;j++){
            if(s[i][j]=='\\'){
                ad(a[i][j],a[i+1][j+1],1);
                ad(a[i+1][j+1],a[i][j],1);
                bb[a[i][j]]=bb[a[i+1][j+1]]=1;
            }
            if(s[i][j]=='/'){
                ad(a[i][j+1],a[i+1][j],1);
                ad(a[i+1][j],a[i][j+1],1);
                bb[a[i][j+1]]=bb[a[i+1][j]]=1;
            }
            if(s[i][j]=='X'){
                ad(a[i][j+1],a[i+1][j],1);
                ad(a[i][j],a[i+1][j+1],1);
                ad(a[i+1][j],a[i][j+1],1);
                ad(a[i+1][j+1],a[i][j],1);
                bb[a[i][j]]=bb[a[i+1][j]]=bb[a[i+1][j+1]]=bb[a[i][j+1]]=1;
            }
        }
    }
    int mans=0;
    for(int i=1;i<=cnt;i++){
        if(bb[i] && !vis[i]){
            ans=0;
            dfs(i);
            if(ans==0) mans+=2;
            else mans+=ans;
        }
    }
    printf("%d\n",mans/2);
    return 0;
}