P4304 [TJOI2013]攻击装置

    • 211通过
    • 566提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 二分图 最大匹配 最大流 各省省选 2013 天津
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一个01矩阵,其中你可以在0的位置放置攻击装置。 每一个攻击装置(x,y)都可以按照“日”字攻击其周围的8个位置(x-1,y-2),(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1),(x+1,y+2),(x+2,y+1)

    求在装置互不攻击的情况下,最多可以放置多少个装置。

    输入输出格式

    输入格式:

    第一行一个整数N,表示矩阵大小为N*N。

    接下来N行每一行一个长度N的01串,表示矩阵。

    输出格式:

    一个整数,表示在装置互不攻击的情况下最多可以放置多少个装置。

    输入输出样例

    输入样例#1: 复制
    3
    010
    000
    100
    输出样例#1: 复制
    4

    说明

    30%数据N<=50

    100%数据 N<=200

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。