雪萌萌的围棋

题目描述

众所周知，雪舞喵有许多猫。

众所周知，<del>前几天</del>很多天前，柯洁和阿尔法苟进行了紧张刺激的围棋比赛，雪舞喵的小猫雪萌萌也心血来潮，要和雪舞喵下围棋，然而雪萌萌和雪舞喵下了 $9223372036854775808$ 场，战绩却是 $0$ 胜 $9223372036854775808$ 负。于是雪萌萌只好去找雪舞喵的小猫雪花花下棋……那当然是不可能的，雪萌萌只会卖萌，怎么可能下的过雪花花。

但是雪萌萌惊喜地发现，她的水平和雪花花最近刚开发出的AI贝塔喵差不多，于是雪萌萌欢天喜地的要和贝塔喵大战 $300$ 回合，然而第一回合刚打完雪萌萌就发愁了，因为根据贝塔喵计算，雪萌萌输了贝塔喵 $368.5$ 目，雪萌萌觉得这个计算显然不对，然而她只会卖萌，又不会计算围棋的胜负，于是她找到了一些闲的五脊六兽的大学生帮她计算她和贝塔喵 $300$ 局棋的胜负。

很不幸，你们就是那些闲的五脊六兽的大学生。围棋的规则大概是这样的，雪萌萌和贝塔喵各自拥有黑棋和白棋，她们在一个共有 $n \times n$ 个点的网格图中下棋，对于每盘棋局的结束状态，每个点上要么存在黑棋，要么存在白棋，要么不存在棋，双方根据自己所占目数多少来决定胜负。

名词约定与解释: (注 : 部分规则不保证等同于真正的围棋规则)

空地的归属 : 如果一块极大的四连通的空地连通块(极大即不存在一个点数更多的空地连通块完全包含这个连通块) 只与黑棋/只与白棋 在四个(上,下,左,右)方向上相邻 ，那么称这块空地归 黑棋/白棋 所有 , 否则 , 这块空地不属于任何一方。 (注 : 不需要像真正的围棋规则一样判断气，死活等，认为给出的状态即为棋局的结束状态)

目数 : 规定一方的目数为 : 一方的棋子数 + 一方所拥有的空地数

贴目 : 为了抵消黑棋先行的优势 , 黑棋需要贴给白棋一定的目数 , 即这些目数将会从黑棋转让给白棋 。

输入

第一行一个整数 $n$ 和一个整数 $d$ , 分别代表棋盘大小和贴目数 。

接下来 $n$ 行每行一个长度为 $n$ 的字符串代表棋局的结束状态（ "B” 为黑棋,“W” 为白棋，“E” 为空地） 。

输出

一行一个整数 $r$ 代表黑棋领先白棋的目数 。

输入样例

5 1
EEBWE
EEBWE
EEBWE
EEBWE
EEBWE

输出样例

3

样例解释

黑棋的目数为 : 10(空地) + 5(黑子) - 1(贴目) = 14

白棋的目数为 : 5(空地) + 5(白子) + 1(贴目) = 11

黑棋领先的目数为 : 14(黑棋目数) - 11(白棋目数) = 3

数据范围

对于前 $10\%$ 的数据 , $ n \le 1 $

对于前 $60\%$ 的数据 , 所有的空地必定属于黑棋或白棋 。

对于前 $80\%$ 的数据 , $ n \le 19 $ 。

对于 $100\%$ 的数据 , $1 \le n \le 50 $ , $\lvert d \rvert \le 2^{31} - 1$

Author : 姜涵书