TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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个数。

    サンプル入力 1

    2 3
    D1
    A3
    C2

    サンプル出力 1

    4

    サンプル入力 2

    6 25
    C12
    B7
    D10
    D12
    A8
    C1
    L2
    E9
    L3
    F6
    F1
    D2
    L6
    D7
    G2
    B9
    L1
    F2
    I6
    B3
    A9
    G3
    B6
    L4
    A5

    サンプル出力 2

    40

    ヒント

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


    ソース  二分图匹配