### 问题描述 给定 $N \times N$ 的网格图，有些网格上有障碍物，现在在网格图上放置若干 $1 \times 2$ 大小的长方形，如果一个网格上已经有障碍物，那么该格子上不能再放置长方形，一个长方形会占据边相邻的 $2$ 个格子，长方形可以旋转，每个网格至多只能被一个长方形覆盖，询问网格上至多能放多少个长方形。 ### 输入格式 第一行包含 $1$ 个正整数 $N$。 之后 $N$ 行，每行给定一个 $01$ 字符串，$0$ 表示该网格上可以放置，$1$ 表示该网格上有障碍物。 ### 输出格式 输出共一行，输出一个整数，表示答案。 ### 样例输入 ```text 3 110 000 100 ``` ### 样例输出 ```text 3 ``` ### 评测数据规模 对于所有测评数据，$1 \leq N \leq 20$。