#P1764. 翻转游戏 (加强版)

翻转游戏 (加强版)

题目描述

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

输入格式

输入的第一行是一个整数n,表示棋盘是n*n的,

接下来有n行,每行包括n个字母,表示初始的棋盘状态。如果字母是w,则表示这个棋子当前是白色向上的,如果字母是b,则表示这个棋子当前是黑色向上的。

输出格式

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

4
bwwb
bbwb
bwwb
bwww
4

提示

【数据范围】

对于30%的数据,1<=n<=4

对于100%的数据,1<=n<=16