/ Vijos / 题库 /

放置机器人

放置机器人

描述

有一个N*M的棋盘,棋盘的每一格是三种类型之一:空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人,若它们之间没有墙,则它们可以互相攻击。问给定的棋盘,最多可以放置多少个机器人,使它们不能互相攻击
图片
如图,白色表示空地,绿色表示草地,黑色表示墙。

格式

输入格式

第1行为两个整数N、M。

接下来N行,每行M个大写字母(只可能是’E’、’G’或’W’,E表示空地,G表示草地,W表示墙壁)。

输出格式

一个整数N,表示最多能放置N个机器人。

样例1

样例输入1

5 5
EGGGW
GWWWG
EEWEE
GGGWE
WEGGE

样例输出1

4

限制

各个测试点1s

提示

对于20%的数据,保证N≤10,M≤10,且空地≤26。

对于100%的数据,保证N≤100,M≤100。

信息

ID
1708
难度
7
分类
图结构 | 二分图 点击显示
标签
(无)
递交数
488
已通过
88
通过率
18%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

湖南师大附中练习赛