P83217

炸弹小人

难度 5 级 初三 动态规划入门
讨论 统计 1通过 4提交 25%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

一个N行M列的网格,在W位置为墙,E位置为敌人。如果将炸弹小人放在位置(i,j)处,则第i行和j列的敌人都会炸死,但如果有墙,则炸弹不能穿透墙。在有敌人的位置和墙的位置都不能放炸弹。例如:

0E0E

E0WE

0E00

放炸弹的最优位置有多个,(1,1)、(2,2)或(3,4),均可以炸死3个敌人。

输入

第一行输入证书N和M。 后面的N行M列为网格。用0表示可以防止炸弹的位置,用1表示敌人,用2表示墙

输出

一个整数,最多能炸死多少人敌人。

样例

样例 1
输入
3 4
0 1 0 1
1 0 2 1
0 1 0 0
输出
3

来源

动规专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交