P1764 翻转游戏 (加强版)

kkke 在一个 $n\ \times n$ 的棋盘上进行一个翻转游戏。棋盘的每个格子上都放有一个棋子，每个棋子有 $2$ 个面，一面是黑色的，另一面是白色的。初始的时候，棋盘上的棋子有的黑色向上，有的白色向上。现在 kkke 想通过最少次数的翻转，使得棋盘上所有的棋子都是同一个颜色向上的（即全是黑色向上的，或全是白色向上的）。每次翻转的时候，kkke 可以选择任意一个棋子，将它翻转，同时，与它上下左右分别相邻的 $4$ 个棋子也必须同时翻转。

无

无

### 数据范围及约定 - 对于 $30\%$ 的数据，$1 \le n \le 4$； - 对于 $100\%$ 的数据，$1 \le n \le 16$。