3979: 【NOIP2022赛前集训】无限水(water)
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：33
解决：10
题目描述
water.in/out/cpp
## 题目描述
1s，512M。
给定一个 $N\times M$ 的矩阵，你需要花费最少桶水使得整个矩阵被填满水。
根据 $\texttt{Minecraft}$ 的世界规则，如果当前格子为空，但与之相邻的格子中有至少 $2$ 个格子有水，则当前格子自动填充一格水。
一直填充下去直到不存在一个空格子有至少 $2$ 个相邻的格子有水。
**形式化题意**：给定一个 $N\times M$ 的矩阵，初始每个格子都是 $0$，你需要将一些格子变成 $1$。之后每一秒，如果存在一个为 $0$ 的格子，与它相邻的最多 $4$ 个格子中，有大于等于两个格子为 $1$，则该格子也会变成 $1$。问初始时至少需要将多少个格子变为 $1$，才能使得整个矩阵最后全部为 $1$。
**注意：不需要使时间最短，如果有多个方案，则输出任意一个**。
## 输入格式
一行两个数表示 $N,M$ 。
## 输出格式
第一行输出一个数表示填充的 $1$ 的数量。
接下来 $N$ 行输出一个 $N\times M$ 的 $0/1$ 矩阵，为 $1$ 表示这个位置填充了一格水，为 $0$ 表示留空。
如果有多个方案，任意输出一个即可。
## 样例 #1
### 样例输入 #1
```
1 2
```
### 样例输出 #1
```
2
1 1
```
## 样例 #2
### 样例输入 #2
```
1 3
```
### 样例输出 #2
```
2
1 0 1
```
## 样例 #3
### 样例输入 #3
```
3 3
```
### 样例输出 #3
```
3
1 0 1
0 0 0
0 1 0
```
## 提示
对于 $100\%$ 的数据，保证 $N\times M\le 10^6$。
- 子任务 1（10 分），$N,M\le 4$。
- 子任务 2（20 分），$N\times M\le 1000$。
- 子任务 3（30 分），$N = M$。
- 子任务 4（40 分），无特殊限制。
样例输入 复制
样例输出 复制