【题解】宫廷守卫 [P1263]

【题目描述】

给出一个 \(n*m\) 的方格图，分别用整数 \(0,1,2\) 表示空地、陷阱、墙，空地上可以放置守卫，如果两个守卫在同一行或同一列且他们之间没有墙的阻挡，那么他们就会互相看见。求最多可以放置多少个守卫使得他们互相无法看见对方，并输出其中一种方案。

【样例】

【数据范围】

\(100 \%:\) \(1 \leqslant n,m \leqslant 200\)

【分析】

如果没有墙的限制，那就是一个果的二分图套路题（車的放置），将每一行看作左点，每一列看作右点，对于没有陷阱的点（空地），将其所在行与其所在列连边，跑一遍二分图最大匹配即可。

墙的存在使得每一行、每一列都分裂成了若干部分，且每一部分都是独立存在、互不干涉的，因此可以把每一部分都视作一个点，例如样例：

第三列 被墙\((2,3)\) 分为了上下两个部分，上面是否放守卫与下面能否放守卫没有任何关联，同理下面也如此。

剩余部分与 車的放置 相同。

【Code】

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define Re register int
using namespace std;
const int N=203,M=80003;
struct QAQ{int to,next;}a[M<<1];
int n,m,o,n1,n2,ans,pan[N*N*2],head[N*N*2],match[N*N*2],A[N][N],idh[N][N],idz[N][N];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int dfs(Re x){//匈牙利算法
    for(Re i=head[x],to;i;i=a[i].next)
        if(!pan[to=a[i].to]){
            pan[to]=1;
            if(!match[to]||dfs(match[to])){
                match[to]=x;return 1;
            }
        }
    return 0;
}
int main(){
    //  freopen("guard.in","r",stdin);
    //  freopen("guard.out","w",stdout);
    in(n),in(m);
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=m;++j)
            in(A[i][j]);
    for(Re i=1;i<=n;++i)A[i][0]=2;//预处理边界
    for(Re i=1;i<=m;++i)A[0][i]=2;
    for(Re i=1;i<=n;++i)//处理每一行
        for(Re j=1;j<=m;++j)
            if(A[i][j]<2)//不是墙，需要建点
                if(A[i][j-1]>1)idh[i][j]=++n1;//前面是墙，新开一部分
                else idh[i][j]=idh[i][j-1];//前面不是墙，与其算作一个部分
    for(Re j=1;j<=m;++j)//处理每一列
        for(Re i=1;i<=n;++i)
            if(A[i][j]<2)//不是墙，需要建点
                if(A[i-1][j]>1)idz[i][j]=++n2;//前面是墙，新开一部分
                else idz[i][j]=idz[i-1][j];//前面不是墙，与其算作一个部分
    for(Re i=1;i<=n;++i)
        for(Re j=1;j<=m;++j)
            if(!A[i][j])add(idh[i][j],idz[i][j]);//没有陷阱就连边
    for(Re i=1;i<=n1;++i){//跑二分图最大匹配
        for(Re j=1;j<=n2;++j)pan[j]=0;
        ans+=dfs(i);
    }
    printf("%d\n",ans);
    for(Re i=1;i<=n;++i)//输出答案利用子匈牙利算法的特性
        for(Re j=1;j<=m;++j)//match数组记录了所有的匹配边
            if(!A[i][j]&&idh[i][j]==match[idz[i][j]])printf("%d %d\n",i,j);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}