[USACO21OPEN] Acowdemia III B

Luogu

IDLGP9939

Time1000ms

Memory256MB

DifficultyP3

贪心USACO2021O2优化分类讨论

Bessie 是一位忙碌的计算机科学研究生。然而，即使是研究生也需要交友。因此，Farmer John 开设了一片草地，目的是为了帮助 Bessie 与其他奶牛建立持久的友谊。 Farmer John 的草地可以被看做是由正方形方格组成的巨大二维方阵（想象一个巨大的棋盘）。每个方格用如下字符标记： - `C`，如果这个方格中有一头奶牛。 - `G`，如果这个方格中有草。 - `.`，如果这个方格既没有奶牛也没有草。对于两头想要成为朋友的奶牛，她们必须选择在一个与她们均水平或竖直方向上相邻的有草方格见面。在这个过程中，她们会在这个有草方格中吃草，所以之后的奶牛不能再使用这个方格作为见面地点。一头奶牛可以与多头其他奶牛成为朋友，但是同一对奶牛不能见面并成为朋友多于一次。 Farmer John 希望有许多奶牛可以见面并成为朋友。请求出当这一活动结束时在奶牛之间可以建立的朋友关系的最大数量。 ## Input 输入的第一行包含 $N$ 和 $M$（$1\le N,M\le 1000$）。以下 $N$ 行每行包含一个由 $M$ 个字符组成的字符串，表示这个草地。 ## Output 输出在这一活动结束时在奶牛之间可以建立的朋友关系的最大数量 [samples] ## Note ### 样例解释 1 如果我们用坐标 $(i,j)$ 标记第 $i$ 行第 $j$ 列的奶牛，则在这个样例中于 $(1,2)$、$(1,5)$、$(2,2)$、$(2,4)$、$(3,1)$、$(3,3)$、$(4,2)$、$(4,3)$ 以及 $(4,5)$ 存在奶牛。一种使四对奶牛成为朋友的方式如下： - 位于 $(2,2)$ 和 $(3,3)$ 的奶牛于 $(3,2)$ 一起吃草。 - 位于 $(2,2)$ 和 $(2,4)$ 的奶牛于 $(2,3)$ 一起吃草。 - 位于 $(2,4)$ 和 $(3,3)$ 的奶牛于 $(3,4)$ 一起吃草。 - 位于 $(2,4)$ 和 $(1,5)$ 的奶牛于 $(2,5)$ 一起吃草。 ### 测试点性质 - 测试点 $2-4$ 满足 $N=2$。 - 测试点 $5-12$ 没有额外限制。

Samples

Input #1

4 5
.CGGC
.CGCG
CGCG.
.CC.C

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[USACO21OPEN] Acowdemia III B",
    "description": {
      "content": "Bessie 是一位忙碌的计算机科学研究生。然而，即使是研究生也需要交友。因此，Farmer John 开设了一片草地，目的是为了帮助 Bessie 与其他奶牛建立持久的友谊。 Farmer John 的草地可以被看做是由正方形方格组成的巨大二维方阵（想象一个巨大的棋盘）。每个方格用如下字符标记：  - `C`，如果这个方格中有一头奶牛。  - `G`，如果这个方格中有草。  - `.`，如果",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9939"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bessie 是一位忙碌的计算机科学研究生。然而，即使是研究生也需要交友。因此，Farmer John 开设了一片草地，目的是为了帮助 Bessie 与其他奶牛建立持久的友谊。\n\nFarmer John 的草地可以被看做是由正方形方格组成的巨大二维方阵（想象一个巨大的棋盘）。每个方格用如下字符标记：\n\n - `C`，如果这个方格中有一头奶牛。\n - `G`，如果这个方格中有草。\n - `.`，如果...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments