Acowdemia III
브론즈 II의견: 0
Bessie is a busy computer science graduate student. However, even graduate
students need friends. As a result, Farmer John has opened a pasture with the
explicit purpose of helping Bessie and other cows form lasting friendships.
Farmer John's pasture can be regarded as a large 2D grid of square "cells"
(picture a huge chess board). Each cell is labeled with:
- C if the cell contains a cow.
- G if the cell contains grass.
- . if the cell contains neither a cow nor grass.
For two distinct cows to become friends, the cows must choose to meet at a
grass-covered square that is directly horizontally or vertically adjacent to
both of them. During the process, they eat the grass in the grass-covered
square, so future pairs of cows cannot use that square as a meeting point. The
same cow may become friends with more than one other cow, but no pair of cows
may meet and become friends more than once.
Farmer John is hoping that numerous pairs of cows will meet and become friends
over time. Please determine the maximum number of new friendships between
distinct pairs of cows that can possibly be created by the end of this
experience.
Problem credits: Benjamin Qi
SCORING
- Test cases 2-4 satisfy \(N=2\).
- Test cases 5-12 satisfy no additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\) and \(M\) (\(N,M \leq 1000\)).
The next \(N\) lines each contain a string of \(M\) characters, describing the pasture.
Count the maximum number of pairs of cows that can become friends by the end
of the experience.
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
평가 및 의견
Acowdemia III
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Acowdemia III