JSP2019——T6题解

· · 个人记录

这道题目是今年江苏省“信息与未来”夏令营的最后一道题目，乍一看这道题目似乎很难的样子，但是我们可以看到:如有多种最优方案 (放置最多数量的小矩形)，输出任意一种即可。 即这道题目使用special judge,所遇我们可以大胆的使用如下这种方法。

当然，在使用这些方法之前，我们先要确定这道题目的读入。

它的读入只会有两个数字，即n和k，在这里，n代表这个矩形的边长，而k代表这个矩形中间障碍的个数。由此我们可以先读入n和k，然后将所有的障碍先处理出来。

int mp[1010][1010],n,k;//其实只要开[60][60]就够了
void Input(){
    cin>>n>>k;

   memset(mp,-1,sizeof(mp));
   for(int i=1;i<=k;i++)mp[i][i]=0;
   //这里我们处理了所有的障碍
}

由于每个障碍都在对角线上，经过探索之后我们可以发现，每个障碍的行和列的坐标都是一样的。所以我们可以这个样子处理。

伪·贪心

这道题目我们最先想到的贪心策略，当然是： 对于每个不是障碍的点，我们可以将其与其四周边向右或者向下没有出界的一个不为障碍的点组成1*2的矩形，若无法成功，这个点就不被标记。

for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mp[i][j]==-1){//这个点还没有被用过，且他不是障碍物
            work(i,j);//我们就对这个点进行操作。
            }
        }
    }

下面我们来写这个至关重要的work函数。首先根据我们的贪心思想，我们需要对每一个点进行操作，那么我们首先要判断这个点有没有出界。

bool inside(int x,int y){return x<=n&&y<=n&&x>0&&y>0;}

然后我们就可以写这个work函数了。

int step=1;

//当前是第step个1*2的矩形

void work(int i,int j){
    if(inside(i+1,j)&&mp[i+1][j]==-1){
        mp[i][j]=mp[i+1][j]=step;//对右边的点进行操作
        step++;
    }else if(inside(i,j+1)&&mp[i][j+1]==-1){
        mp[i][j]=mp[i][j+1]=step;//对下面的点进行操作
        step++;
    }
}

然后我们就可以开始输出了：

void print(){
    for(int i=1;i<=n;i++){
    for(int j-1lj<=n;j++){
        cout<<done(mp[i][j]<<' ';
    }
    cout<<endl;
  }
}

然后就是这个done函数。由于我们在一开始的时候就将其全部赋值为了-1， 所以我们将其与0取大就可以了。

int done(int p){return max(p,0);}

OK，完美。

贴上代码：

include<bits/stdc++.h>
using namespace std;
int mp[1010][1010];
int n,k;
bool inside(int x,int y){
    return x<=n&&y<=n;
}
int main(){
    cin>>n>>k;
    memset(mp,-1,sizeof(mp));
    for(int i=1;i<=k;i++)mp[i][i]=0;

    int step=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mp[i][j]==-1){
                if(inside(i+1,j)&&mp[i+1][j]==-1){
                    mp[i][j]=mp[i+1][j]=step;
                    step++;
                }else if(inside(i,j+1)&&mp[i][j+1]==-1){
                    mp[i][j]=mp[i][j+1]=step;
                    step++;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cout<<max(mp[i][j],0)<<' ';
        cout<<endl;
    }
    return 0;
}