레이팅 미적용베시는 바쁜 컴퓨터 과학 대학원생이다. 하지만 대학원생에게도 친구는 필요하다. 그래서 농부 존은 베시와 다른 소들이 오래가는 우정을 쌓도록 돕겠다는 명확한 목적으로 목초지를 개방했다.
농부 존의 목초지는 정사각형 "칸"들로 이루어진 커다란 2차원 격자(거대한 체스판을 떠올려 보자)로 생각할 수 있다. 각 칸은 다음과 같이 표시된다:
- C: 칸에 소가 있다.
- G: 칸에 풀이 있다.
- .: 칸에 소도 풀도 없다.
서로 다른 두 소가 친구가 되려면, 두 소 모두와 가로 또는 세로로 바로 인접한, 풀이 덮인 칸에서 만나기로 해야 한다. 그 과정에서 두 소는 그 칸의 풀을 먹어 버리므로, 이후의 소 쌍은 그 칸을 만남의 장소로 사용할 수 없다. 같은 소가 여러 소와 친구가 될 수는 있지만, 어떤 소 쌍도 두 번 이상 만나 친구가 될 수는 없다.
농부 존은 시간이 지나면서 수많은 소 쌍이 만나 친구가 되기를 바라고 있다. 이 경험이 끝날 때까지 만들어질 수 있는, 서로 다른 소 쌍 사이의 새로운 우정의 최대 개수를 구하라.
문제 제공: Benjamin Qi
채점 방식
- 테스트 케이스 2-4는 \(N=2\)를 만족한다.
- 테스트 케이스 5-12는 추가 제약이 없다.
문제 제공: Benjamin Qi
첫째 줄에 \(N\)과 \(M\)이 주어진다 (\(N,M \leq 1000\)).
다음 \(N\)개의 줄에는 각각 \(M\)개의 문자로 이루어진 문자열이 주어지며, 이는 목초지를 나타낸다.
이 경험이 끝날 때까지 친구가 될 수 있는 소 쌍의 최대 개수를 출력한다.
4 5
.CGGC
.CGCG
CGCG.
.CC.C4If we label the cow in row \(i\) and column \(j\) with coordinates \((i,j)\), then in
this example there are cows at \((1,2)\), \((1,5)\), \((2,2)\), \((2,4)\), \((3,1)\), \((3,3)\), \((4,2)\),
\((4,3)\), and \((4,5)\). One way for four pairs of cows to become friends is as
follows:
- The cows at \((2,2)\) and \((3,3)\) eat the grass at \((3,2)\).
- The cows at \((2,2)\) and \((2,4)\) eat the grass at \((2,3)\).
- The cows at \((2,4)\) and \((3,3)\) eat the grass at \((3,4)\).
- The cows at \((2,4)\) and \((1,5)\) eat the grass at \((2,5)\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > US Open > Bronze