logo AlgoBeat OnlineJudge
登录 注册

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

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

输入格式

输入的第一行是一个整数 ,表示棋盘的大小是

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

输出格式

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

样例

样例输入 1

4
bwwb
bbwb
bwwb
bwww

样例输出 1

4

数据范围与提示

数据范围及约定

  • 对于 的数据,
  • 对于 的数据,