题解：B3755 [信息与未来 2019] 方格覆盖

## 前言
祝审核和看见这篇题解的人事事顺心！ヽ(≧∀≦)ﾉ(≧ω≦)/

## 题目描述
题目传送门（https://www.luogu.com.cn/problem/B3755 ）

## 题目简要
我们需要在一个 n×n 的矩形上放置最多的 1×2 的小矩形 （只可以水平或垂直放置），对角线上的 k 个连续障碍物不可放置。 而且如有多种最优方案，输出任意一种即可。

## 解题思路
- 首先看看是不是障碍物，沿对角线赋值为 -1（方便后面判断）
- 使用贪心思想，
先判断垂直（竖着）可不可以，即判断该格与下面的格子a[i-1][j]是不是都可以放置（两个格子都是0,既不是障碍也没有放过其他小矩形）。如果不行，再判断水平（横着）可不可以，判断该格与右面的格子a[i][j-1]是不是都可以放置（与上述同理）。
- **！！不要忘记判断判断边缘！！**
- 使用变量r从一开始累加，表示序号。
~~因为上面的*输出任意一种即可，所以也不需要太复杂。~~

## CODE 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,k,a[55][55],r=1;
int main() {
	cin>>n>>k;
	for(int i=1; i<=k; i++) a[i][i]=-1;//对角线障碍物
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(a[i][j]==0) {
				if(i+1<=n&&a[i+1][j]==0) { //垂直判断&边缘
					a[i][j]=r;
					a[i+1][j]=r;
					r++;
				}
        else if(j+1<=n&&a[i][j+1]==0) { //水平判断&边缘
					a[i][j]=r;
					a[i][j+1]=r;
					r++;
				}
			}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) 
			if(a[i][j]==-1) cout<<"0 "; //加！空格（钠）！
		else cout<<a[i][j]<<" "; 
		cout<<endl; //换行哟
	}
	return 0;//完结撒花❁✿ヽ(^▽^)ノ✿❉
}
```
感谢阅读Thanks♪(･ω･)ﾉ！ 我们下次再见ヾ(￣▽￣)Bye~Bye~！

正在渲染内容...