A1847 | $翻转游戏 (加强版)$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输入的第一行是一个整数 $n$，表示棋盘的大小是 $n\times n$。 接下来有 $n$ 行，每行包括 $n$ 个字母，表示初始的棋盘状态。如果字母是 $\tt w$，则表示这个棋子当前是白色向上的，如果字母是 $\tt b$，则表示这个棋子当前是黑色向上的。

输出为一行，如果无法翻转出目标状态，则输出 Impossible ，否则输出一个整数，表示 AC酱最少需要翻转的次数。

输入 #1

4
bwwb
bbwb
bwwb
bwww

输出 #1

C++ 编辑器

输入

输出