#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