TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1521
  • 题目
  • P1521芯片制作
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

       计算机的大脑通常被称为CPU。
    现在国家XX局交给小A一个重要任务,要求他制作一种新型的CPU,幸运的是,CPU研究中心已经将好多个CPU内核蚀刻在硅片上了,这种硅片很可爱,它是由3n^2个内核拼成的L型。当n=5的时候,硅片的形状如下图所示。小A的任务就是把CPU内核从硅片上切割下来,封装在一个铜盒子里拿出来卖钱。


       由于技术原因,CPU的蚀刻有可能失败,如果某个CPU内核蚀刻失败了,它就不能卖钱了。在上图中,有3个内核蚀刻失败,蚀刻失败的内核的坐标分别是C4,F2,G5。显然,如果硅片上有m个CPU内核蚀刻失败了,则有3n2-m个内核是可以卖钱的,如果每个CPU内只装1个内核(这就是传统的单核处理器),此时你就可以做出3n2-m个CPU。
      小A雇用了你来替他完成这个东西。他把所有任务都交给了你。突然,国家发展和改革委员会决定要发展双核处理器技术。你要做的是双核处理器了。上司告诉你,如果在L型硅片上任意两个相邻的CPU内核都是完好的,那么你就可以把它们一起切下来做成一个双核CPU。所谓相邻,指的是CPU内核有一条公共边界。
       由于你的薪水是按照做出的CPU的个数决定的,现在你想算算最多能切出多少个双核的CPU。

    输入格式

       第一行包含2个整数n,k
    以下K行,每行包括一个字母和紧跟着的一个整数,代表一个蚀刻失败的CPU的坐标。文件保证坐标在L型硅片内。

    输出格式

       一行,仅包含一个整数,代表能切出的最多双核CPU个数。

    样例输入

    2 3
    D1
    A3
    C2

    样例输出

    4

    提示

       在100%的数据中2<=n<=7, 0.1n2<=k<=3n^2。


    来源  二分图匹配