题解：P6809 [BalticOI 2010 Day2] Mines

Judgelight · 2024-10-14 11:52:41 · 题解

假设没有雷为 0，有雷为 1。

我们首先去枚举 (1,1) 这个位置的值，我们设它是 z，套用主元法，设第一列的所有位置 (i,1) 的值为 a_{i-1}，第一行的所有位置 (1,i) 的值为 b_{i-1}，忽略所有常数，以 4\times 4 的网格为例，我们可以得到下面这张表：

打表可以发现每个位置只与它所在行列对应的 a,b 有关，且系数绝对值不超过 1，所以我们的限制本质上是 a_i\pm b_i\in [l,r]。我们还有一个限制就是 a_i,b_i\in [0,1]。这启示我们把这个东西拿来跑 2-SAT。

还有一个问题是关于最后一行和最后一列的限制我们是没有用到的，这个地方单独处理，算出来一些 a_i,b_i，把它们当做常数即可，时间复杂度为严格的 O(nm)，但是带大概 8 的常数。

代码（仅供参考）：

#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define mk make_pair
#define N 2009
#define Abs(x) ((x)>0?x:-x)
#define _2 0x3f3f3f3f
using namespace std;
inline char nc(){ static char buf[1000000],*p=buf,*q=buf; return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++; } inline int rd(){ int res = 0; char c = nc(); while(c<'0'||c>'9')c=nc(); while(c<='9'&&c>='0')res=res*10+c-'0',c=nc(); return res; } char obuf[1<<21],*p3=obuf; inline void pc(char c){ p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); } inline void wt(int x){ if(x<0) pc('-'),x=-x; if(x>9) wt(x/10); pc(x%10+'0'); }
const int dx[9]={-1,-1,-1,0,0,0,1,1,1},dy[9]={-1,0,1,-1,0,1,-1,0,1};
int n,m,a[N][N];char c[N][N];
pair<int,int>p[N][N];int r[N][N];
int va[N],vb[N];
vector<int>aa[N<<1],bb[N<<1];int X[N<<1];int idx;bool del[N<<1];
struct sat2{
    #undef N
    #define N 8009
    #define M 10000009
    #define g(a,b) (a+(b?0:n))
    int n,m;bitset<N>e[N];
    inline void add(int u,int v){e[u][v]=1;}
    int stk[N],top,instk[N],dfn[N],low[N],timestamps,id[N],scnt;
    void tarjan(int u){
        stk[++top]=u,instk[u]=1,dfn[u]=low[u]=++timestamps;
        for(int v=e[u]._Find_first();v!=e[u].size();v=e[u]._Find_next(v)){
            if(!dfn[v]){
                tarjan(v),low[u]=min(low[u],low[v]);
            }
            else if(instk[v])low[u]=min(low[u],dfn[v]);
        }
        if(dfn[u]==low[u]){
            int v;scnt++;
            do{
                v=stk[top--],instk[v]=0;
                id[v]=scnt;
            }
            while(v!=u);
        }
    }
    inline void add(int p,int a,int q,int b){add(g(p,a),g(q,b));}
    int c[N];
    bool solve(int n){
        for(int i=1;i<=(n<<1);i++)if(!dfn[i])tarjan(i);
        for(int i=1;i<=n;i++)if(id[g(i,0)]==id[g(i,1)])return 0;
        for(int i=1;i<=n;i++)c[i]=id[g(i,1)]<id[g(i,0)];
        return 1;
    }
    void clean(){
        for(int i=1;i<=(n<<1);i++)e[i].reset();
        memset(stk,0,sizeof(stk)),top=0,memset(instk,0,sizeof(instk)),memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),timestamps=0,memset(id,0,sizeof(id)),scnt=0;
    }
}T;
signed main(){
    //freopen("ex_minesweeper5.in","r",stdin);
    //freopen("Misaka.txt","w",stdout);
    n=rd(),m=rd();
    for(int i=1;i<=n;i++)va[i]=_2;for(int i=1;i<=m;i++)vb[i]=_2;
    for(int i=1;i<=n;i++){
        char ch=nc();
        while(ch<'0'||ch>'9')ch=nc();
        int nw=0;
        while(ch>='0'&&ch<='9'){
            c[i][++nw]=ch,ch=nc();
        }
        for(int j=1;j<=m;j++)a[i][j]=c[i][j]-'0';
    }
    r[1][1]=0;
    for(int i=2;i<=n;i++)p[i][1]=mk(i-1,0);
    for(int i=2;i<=m;i++)p[1][i]=mk(0,i-1);
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            int x=a[i-1][j-1];
            for(int t=0;t<9;t++){
                int ii=i-1+dx[t],jj=j-1+dy[t];
                if(ii<=0||jj<=0||ii>n||jj>m||(ii==i&&jj==j))continue;
                p[i][j].first-=p[ii][jj].first,p[i][j].second-=p[ii][jj].second;
                x-=r[ii][jj];
            }
            r[i][j]=x;
        }
    }
    for(int i=1;i<=n;i++){
        map<int,int>ma,mb;idx++;X[idx]=a[i][m];
        for(int t=0;t<9;t++){
            int ii=i+dx[t],jj=m+dy[t];
            if(ii<=0||jj<=0||ii>n||jj>m)continue;
            ma[Abs(p[ii][jj].first)]+=p[ii][jj].first,mb[Abs(p[ii][jj].second)]+=p[ii][jj].second;
            X[idx]-=r[ii][jj];
        }
        for(auto x:ma){
            if(x.second!=0)aa[idx].eb(x.second);
        }
        for(auto x:mb){
            if(x.second!=0)bb[idx].eb(x.second);
        }
    }
    for(int i=1;i<=m;i++){
        map<int,int>ma,mb;idx++;X[idx]=a[n][i];
        for(int t=0;t<9;t++){
            int ii=n+dx[t],jj=i+dy[t];
            if(ii<=0||jj<=0||ii>n||jj>m)continue;
            ma[Abs(p[ii][jj].first)]+=p[ii][jj].first,mb[Abs(p[ii][jj].second)]+=p[ii][jj].second;
            X[idx]-=r[ii][jj];
        }
        for(auto x:ma){
            if(x.second!=0)aa[idx].eb(x.second);
        }
        for(auto x:mb){
            if(x.second!=0)bb[idx].eb(x.second);
        }
    }
    for(int t=1;;t++){
        bool flag=0;
        for(int i=1;i<=idx;i++){
            if(del[i])continue;
            vector<int>a,b;int Y=X[i];
            for(auto x:aa[i]){
                if(va[Abs(x)]!=_2)Y-=(x/Abs(x))*va[Abs(x)];
                else a.eb(x);
            }
            for(auto x:bb[i]){
                if(vb[Abs(x)]!=_2)Y-=(x/(Abs(x)))*vb[Abs(x)];
                else b.eb(x);
            }
            if(a.size()==1&&b.size()==0){
                flag=1;
                del[i]=1;va[Abs(a[0])]=(a[0]/Abs(a[0]))*Y;
                aa[i]=a,bb[i]=b,X[i]=Y;
                continue;
            }
            if(b.size()==1&&a.size()==0){
                flag=1;
                del[i]=1;vb[Abs(b[0])]=(b[0]/Abs(b[0]))*Y;
                aa[i]=a,bb[i]=b,X[i]=Y;
                continue;
            }
            aa[i]=a,bb[i]=b,X[i]=Y;
        }
        if(!flag)break;
    }
    bool flag=0;
    for(int i=1;i<n;i++)if(va[i]!=_2&&va[i]!=0&&va[i]!=1){flag=1;break;}
    for(int i=1;i<m;i++)if(vb[i]!=_2&&vb[i]!=0&&vb[i]!=1){flag=1;break;}
    if(!flag){
        T.n=n+m-2;
        for(int i=1;i<n;i++)if(va[i]!=_2)T.add(i,va[i]^1,i,va[i]);
        for(int i=1;i<m;i++)if(vb[i]!=_2)T.add(i+n-1,vb[i]^1,i,vb[i]);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(p[i][j].first!=0&&va[Abs(p[i][j].first)]!=_2){
                    r[i][j]+=(p[i][j].first/Abs(p[i][j].first))*va[Abs(p[i][j].first)],p[i][j].first=0;
                }
                if(p[i][j].second!=0&&vb[Abs(p[i][j].second)]!=_2){
                    r[i][j]+=(p[i][j].second/Abs(p[i][j].second))*vb[Abs(p[i][j].second)],p[i][j].second=0;
                }
                if(p[i][j].first==0&&p[i][j].second==0)continue;
                if(p[i][j].second==0){
                    int L=0-r[i][j],R=1-r[i][j];if(p[i][j].first<0)L=-L,R=-R,swap(L,R);
                    int x=Abs(p[i][j].first);
                    if(L==1)T.add(x,0,x,1);
                    if(R==0)T.add(x,1,x,0);
                }
                else if(p[i][j].first==0){
                    int L=0-r[i][j],R=1-r[i][j];if(p[i][j].second<0)L=-L,R=-R,swap(L,R);
                    int x=Abs(p[i][j].second)+n-1;
                    if(L==1)T.add(x,0,x,1);
                    if(R==0)T.add(x,1,x,0);
                }
                else{
                    int x=Abs(p[i][j].first),y=Abs(p[i][j].second)+n-1;int L=0-r[i][j],R=1-r[i][j];
                    if(p[i][j].first>0&&p[i][j].second>0){
                        if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,x+y!=0
                        if(1<L||1>R)T.add(x,0,y,0);//x=0,y!=1,x+y!=1
                        if(1<L||1>R)T.add(x,1,y,1);//x=1,y!=0,x+y!=1
                        if(2<L||2>R)T.add(x,1,y,0);//x=1,y!=1,x+y!=2
                        //
                        if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,x+y!=0
                        if(1<L||1>R)T.add(y,0,x,0);//y=0,x!=1,x+y!=1
                        if(1<L||1>R)T.add(y,1,x,1);//y=1,x!=0,x+y!=1
                        if(2<L||2>R)T.add(y,1,x,0);//y=1,x!=1,x+y!=2
                    }
                    else if(p[i][j].first>0&&p[i][j].second<0){
                        if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,x-y!=0
                        if(-1<L||-1>R)T.add(x,0,y,0);//x=0,y!=1,x-y!=-1
                        if(1<L||1>R)T.add(x,1,y,1);//x=1,y!=0,x-y!=1
                        if(0<L||0>R)T.add(x,1,y,0);//x=1,y!=1,x-y!=0
                        //
                        if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,x-y!=0
                        if(1<L||1>R)T.add(y,0,x,0);//y=0,x!=1,x-y!=1
                        if(-1<L||-1>R)T.add(y,1,x,1);//y=1,x!=0,x-y!=-1
                        if(0<L||0>R)T.add(y,1,x,0);//y=1,x!=1,x-y!=0
                    }
                    else if(p[i][j].first<0&&p[i][j].second>0){
                        if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,y-x!=0
                        if(-1<L||-1>R)T.add(y,0,x,0);//y=0,x!=1,y-x!=-1
                        if(1<L||1>R)T.add(y,1,x,1);//y=1,x!=0,y-x!=1
                        if(0<L||0>R)T.add(y,1,x,0);//y=1,x!=1,y-x!=0
                        //
                        if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,y-x!=0
                        if(1<L||1>R)T.add(x,0,y,0);//x=0,y!=1,y-x!=1
                        if(-1<L||-1>R)T.add(x,1,y,1);//x=1,y!=0,y-x!=-1
                        if(0<L||0>R)T.add(x,1,y,0);//x=1,y!=1,y-x!=0
                    }
                    else{
                        if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,-x-y!=0
                        if(-1<L||-1>R)T.add(x,0,y,0);//x=0,y!=1,-x-y!=-1
                        if(-1<L||-1>R)T.add(x,1,y,1);//x=1,y!=0,-x-y!=-1
                        if(-2<L||-2>R)T.add(x,1,y,0);//x=1,y!=1,-x-y!=-2
                        //
                        if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,-x-y!=0
                        if(-1<L||-1>R)T.add(y,0,x,0);//y=0,x!=1,-x-y!=-1
                        if(-1<L||-1>R)T.add(y,1,x,1);//y=1,x!=0,-x-y!=-1
                        if(-2<L||-2>R)T.add(y,1,x,0);//y=1,x!=1,-x-y!=-2
                    }
                }
            }
        }
        if(T.solve(n+m-2)){
            for(int i=1;i<n;i++)va[i]=T.c[i];
            for(int i=1;i<m;i++)vb[i]=T.c[i+n-1];
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++){
                    int x=r[i][j];
                    if(p[i][j].first)x+=va[Abs(p[i][j].first)]*(p[i][j].first/Abs(p[i][j].first));
                    if(p[i][j].second)x+=vb[Abs(p[i][j].second)]*(p[i][j].second/(Abs(p[i][j].second)));
                    x==0?pc('0'):pc('1');
                }
                pc('\n');
            }
            fwrite(obuf,p3-obuf,1,stdout);
            return 0;
        }
    }
    /////////////////////////////////////////////////////////////////
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)p[i][j]=mk(0,0);for(int i=1;i<=n+m;i++)aa[i].clear(),bb[i].clear(),X[i]=0,del[i]=0;idx=0;
    T.clean();
    memset(r,0,sizeof(r)),memset(va,0,sizeof(va)),memset(vb,0,sizeof(vb));
    for(int i=1;i<=n;i++)va[i]=_2;for(int i=1;i<=m;i++)vb[i]=_2;
    r[1][1]=1;
    for(int i=2;i<=n;i++)p[i][1]=mk(i-1,0);
    for(int i=2;i<=m;i++)p[1][i]=mk(0,i-1);
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            int x=a[i-1][j-1];
            for(int t=0;t<9;t++){
                int ii=i-1+dx[t],jj=j-1+dy[t];
                if(ii<=0||jj<=0||ii>n||jj>m||(ii==i&&jj==j))continue;
                p[i][j].first-=p[ii][jj].first,p[i][j].second-=p[ii][jj].second;
                x-=r[ii][jj];
            }
            r[i][j]=x;
        }
    }
    for(int i=1;i<=n;i++){
        map<int,int>ma,mb;idx++;X[idx]=a[i][m];
        for(int t=0;t<9;t++){
            int ii=i+dx[t],jj=m+dy[t];
            if(ii<=0||jj<=0||ii>n||jj>m)continue;
            ma[Abs(p[ii][jj].first)]+=p[ii][jj].first,mb[Abs(p[ii][jj].second)]+=p[ii][jj].second;
            X[idx]-=r[ii][jj];
        }
        for(auto x:ma){
            if(x.second!=0)aa[idx].eb(x.second);
        }
        for(auto x:mb){
            if(x.second!=0)bb[idx].eb(x.second);
        }
    }
    for(int i=1;i<=m;i++){
        map<int,int>ma,mb;idx++;X[idx]=a[n][i];
        for(int t=0;t<9;t++){
            int ii=n+dx[t],jj=i+dy[t];
            if(ii<=0||jj<=0||ii>n||jj>m)continue;
            ma[Abs(p[ii][jj].first)]+=p[ii][jj].first,mb[Abs(p[ii][jj].second)]+=p[ii][jj].second;
            X[idx]-=r[ii][jj];
        }
        for(auto x:ma){
            if(x.second!=0)aa[idx].eb(x.second);
        }
        for(auto x:mb){
            if(x.second!=0)bb[idx].eb(x.second);
        }
    }
    for(int t=1;;t++){
        bool flag=0;
        for(int i=1;i<=idx;i++){
            if(del[i])continue;
            vector<int>a,b;int Y=X[i];
            for(auto x:aa[i]){
                if(va[Abs(x)]!=_2)Y-=(x/Abs(x))*va[Abs(x)];
                else a.eb(x);
            }
            for(auto x:bb[i]){
                if(vb[Abs(x)]!=_2)Y-=(x/(Abs(x)))*vb[Abs(x)];
                else b.eb(x);
            }
            if(a.size()==1&&b.size()==0){
                flag=1;
                del[i]=1;va[Abs(a[0])]=(a[0]/Abs(a[0]))*Y;
                aa[i]=a,bb[i]=b,X[i]=Y;
                continue;
            }
            if(b.size()==1&&a.size()==0){
                flag=1;
                del[i]=1;vb[Abs(b[0])]=(b[0]/Abs(b[0]))*Y;
                aa[i]=a,bb[i]=b,X[i]=Y;
                continue;
            }
            aa[i]=a,bb[i]=b,X[i]=Y;
        }
        if(!flag)break;
    }
    T.n=n+m-2;
    for(int i=1;i<n;i++)if(va[i]!=_2)T.add(i,va[i]^1,i,va[i]);
    for(int i=1;i<m;i++)if(vb[i]!=_2)T.add(i+n-1,vb[i]^1,i,vb[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(p[i][j].first!=0&&va[Abs(p[i][j].first)]!=_2){
                r[i][j]+=(p[i][j].first/Abs(p[i][j].first))*va[Abs(p[i][j].first)],p[i][j].first=0;
            }
            if(p[i][j].second!=0&&vb[Abs(p[i][j].second)]!=_2){
                r[i][j]+=(p[i][j].second/Abs(p[i][j].second))*vb[Abs(p[i][j].second)],p[i][j].second=0;
            }
            if(p[i][j].first==0&&p[i][j].second==0)continue;
            if(p[i][j].second==0){
                int L=0-r[i][j],R=1-r[i][j];if(p[i][j].first<0)L=-L,R=-R,swap(L,R);
                int x=Abs(p[i][j].first);
                if(L==1)T.add(x,0,x,1);
                if(R==0)T.add(x,1,x,0);
            }
            else if(p[i][j].first==0){
                int L=0-r[i][j],R=1-r[i][j];if(p[i][j].second<0)L=-L,R=-R,swap(L,R);
                int x=Abs(p[i][j].second)+n-1;
                if(L==1)T.add(x,0,x,1);
                if(R==0)T.add(x,1,x,0);
            }
            else{
                int x=Abs(p[i][j].first),y=Abs(p[i][j].second)+n-1;int L=0-r[i][j],R=1-r[i][j];
                if(p[i][j].first>0&&p[i][j].second>0){
                    if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,x+y!=0
                    if(1<L||1>R)T.add(x,0,y,0);//x=0,y!=1,x+y!=1
                    if(1<L||1>R)T.add(x,1,y,1);//x=1,y!=0,x+y!=1
                    if(2<L||2>R)T.add(x,1,y,0);//x=1,y!=1,x+y!=2
                    //
                    if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,x+y!=0
                    if(1<L||1>R)T.add(y,0,x,0);//y=0,x!=1,x+y!=1
                    if(1<L||1>R)T.add(y,1,x,1);//y=1,x!=0,x+y!=1
                    if(2<L||2>R)T.add(y,1,x,0);//y=1,x!=1,x+y!=2
                }
                else if(p[i][j].first>0&&p[i][j].second<0){
                    if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,x-y!=0
                    if(-1<L||-1>R)T.add(x,0,y,0);//x=0,y!=1,x-y!=-1
                    if(1<L||1>R)T.add(x,1,y,1);//x=1,y!=0,x-y!=1
                    if(0<L||0>R)T.add(x,1,y,0);//x=1,y!=1,x-y!=0
                    //
                    if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,x-y!=0
                    if(1<L||1>R)T.add(y,0,x,0);//y=0,x!=1,x-y!=1
                    if(-1<L||-1>R)T.add(y,1,x,1);//y=1,x!=0,x-y!=-1
                    if(0<L||0>R)T.add(y,1,x,0);//y=1,x!=1,x-y!=0
                }
                else if(p[i][j].first<0&&p[i][j].second>0){
                    if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,y-x!=0
                    if(-1<L||-1>R)T.add(y,0,x,0);//y=0,x!=1,y-x!=-1
                    if(1<L||1>R)T.add(y,1,x,1);//y=1,x!=0,y-x!=1
                    if(0<L||0>R)T.add(y,1,x,0);//y=1,x!=1,y-x!=0
                    //
                    if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,y-x!=0
                    if(1<L||1>R)T.add(x,0,y,0);//x=0,y!=1,y-x!=1
                    if(-1<L||-1>R)T.add(x,1,y,1);//x=1,y!=0,y-x!=-1
                    if(0<L||0>R)T.add(x,1,y,0);//x=1,y!=1,y-x!=0
                }
                else{
                    if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,-x-y!=0
                    if(-1<L||-1>R)T.add(x,0,y,0);//x=0,y!=1,-x-y!=-1
                    if(-1<L||-1>R)T.add(x,1,y,1);//x=1,y!=0,-x-y!=-1
                    if(-2<L||-2>R)T.add(x,1,y,0);//x=1,y!=1,-x-y!=-2
                    //
                    if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,-x-y!=0
                    if(-1<L||-1>R)T.add(y,0,x,0);//y=0,x!=1,-x-y!=-1
                    if(-1<L||-1>R)T.add(y,1,x,1);//y=1,x!=0,-x-y!=-1
                    if(-2<L||-2>R)T.add(y,1,x,0);//y=1,x!=1,-x-y!=-2
                }
            }
        }
    }
    if(T.solve(n+m-2)){
        for(int i=1;i<n;i++)va[i]=T.c[i];
        for(int i=1;i<m;i++)vb[i]=T.c[i+n-1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int x=r[i][j];
                if(p[i][j].first)x+=va[Abs(p[i][j].first)]*(p[i][j].first/Abs(p[i][j].first));
                if(p[i][j].second)x+=vb[Abs(p[i][j].second)]*(p[i][j].second/(Abs(p[i][j].second)));
                x==0?pc('0'):pc('1');
            }
            pc('\n');
        }
        fwrite(obuf,p3-obuf,1,stdout);
        return 0;
    }
    return 0;
}