P10172

Exoplanetary_Mirage · 2024-03-14 21:10:18 · 题解

一种 n>3 时也能过的方法。

做法

首先，当有 (i,j) 满足四联通块中被取走的石子数量 >1 时，这个肯定不能取。

其次，当有 (i,j) 满足四联通块中被取走的石子数量 =1 时，肯定直接取。

最后，当有 (i,j) 满足四联通块中被取走的石子数量 =0 且 j\in[1,m-1] 时，我们可以先取 (i,j+1) 再取 (i,j)。

正确性证明

你说得对，但四联通 \ge 1 时，正确性很明显。

其次，根据上述取法的矩阵肯定不存在连续两个都没取的情况。

那么 (i,j) 四联通 =0 时，(i-1,j+1) 肯定已经被取，所以如果直接取 (i,j)，(i,j+1) 的四联通数量肯定 \ge 2。

但是如果先取 (i,j+1)，(i,j) 的四联通仅为 1，还可以取掉 (i,j)，这样就实现了数量最大化。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=15,M=1e5+5;
int n,m;
int vis[N][M],cnt;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int count(int x,int y){
    int ans=0;
    for(int i=0;i<4;i++){
        if(vis[x+dx[i]][y+dy[i]]!=-1){
            ans++;
        }
    }
    return ans;
}

void pick(int x,int y){
    vis[x][y]=++cnt;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    memset(vis,-1,sizeof(vis));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(vis[i][j]!=-1) continue;
            if(count(i,j)==0&&j!=m){
                pick(i,j+1);
            }
            if(count(i,j)<=1){
                pick(i,j);
            }
        }
    }
    cout<<cnt<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<vis[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}