模拟战役
题号:NC14698
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

齐齐和司机在玩单机游戏《红色警戒IV》,现在他们的游戏地图被划分成一个n*m的方格地图。齐齐的基地在最上方的4行格内,司机的基地在最下方的4行格内。他们只有一种攻击方式:远程大炮,相关属性如下:
1、    大炮可以打到地图的任意一个位置。
2、    双方每次必须动用本方的一门大炮攻击,齐齐先手,双方交替进行攻击。
3、    一方大炮只能攻击另一方大炮,不能攻击本方或强制攻击未获得视野的地区。
4、    被一方大炮击中的另一方大炮会产生以攻击点为中心3*3的波及区域,波及区域内如果有其他大炮则也会产生3*3的波及区域。
5、    两方的基地相距很远,所以不存在攻打敌方大炮时波及到本方大炮的情况。
齐齐偷偷开了“间谍卫星”,所以他能看到司机的大炮部署,司机则无视野。但如果齐齐做出攻击,司机会立即获取到发动攻击的大炮的视野,并在回合开始时动用大炮(如果存在的话)将其摧毁(摧毁后可能产生的连锁不计入视野)。
现在给出齐齐和司机的大炮部署,问齐齐在选择最优的策略下,在摧毁所有司机的大炮后可以保留最多几门本方大炮。

输入描述:

第1行输入一个整数m,表示地图的宽度。
第2-5行,每行输入一串长度为m的字符串,代表司机的大炮部署。(大炮为"*"号,空地为“.”号)
第6-9行,每行输入一串长度为m的字符串,代表齐齐的大炮部署。(大炮为"*"号,空地为“.”号)
数据保证:0<m≤100

输出描述:

输出一行,一个整数。代表摧毁所有司机的大炮后最多保留几门大炮。如果不能摧毁所有司机的大炮,则输出-1。
示例1

输入

复制
3
...
.*.
..*
*..
*..
.**
...
*.*

输出

复制
4
示例2

输入

复制
3
*..
..*
...
...
...
...
.*.
...

输出

复制
-1