双色棋盘

题目描述:

在一个 n×n 的棋盘中，每个方格都有颜色：要么是颜色 0 ，要么是颜色 1。
用一些 1×2 的卡片覆盖棋盘，要求一张卡片要正好覆相邻且同色的正常方格，卡片不能重叠。
试求：在上述规则下，卡片最多能覆盖多少方格。

输入格式:

第 1 行有一个整数 n，表示棋盘边长。
在接下来的 n 行中，每行有 n 个数，表示棋盘颜色。

输出格式:

输出一个整数，表示能覆盖多少方格。

样例输入:

5
0 1 1 1 0
0 1 1 0 1
1 1 0 1 1
1 1 0 1 0
0 1 0 1 1

样例输出:

18

提示:

1≤n≤300。

时间限制: 1000ms
空间限制: 256MB

---