はまやんはまやんはまやん

hamayanhamayan's blog

Chef And his Cake [CodeChef December Challenge 2017 A]

https://www.codechef.com/DEC17/problems/GIT01
RとGからなる横M,縦Nの盤面が与えられる。
RをGにする時はコスト5かかり、GをRにするにはコスト3かかる。
RとGの市松模様にするための最小コストは?

解法

RGRGRGRG
GRGRGRGR
RGRGRGRG
GRGRGRGR
とするか、
GRGRGRGR
RGRGRGRG
GRGRGRGR
RGRGRGRG
とするかの2択なので、どちらとも試してみて、コストが小さい方を答える。

int N, M;
string B[101];
//---------------------------------------------------------------------------------------------------
string RG = "RG";
void solve() {
    cin >> N >> M;
    rep(y, 0, N) cin >> B[y];

    int ans = 10101010;
    rep(d, 0, 2) {
        int cnt = 0;
        rep(y, 0, N) rep(x, 0, M) {
            int c = (x + y) % 2;
            c = (c + d) % 2;
            if (B[y][x] != RG[c]) {
                if (B[y][x] == 'R') cnt += 5;
                else cnt += 3;
            }
        }
        ans = min(ans, cnt);
    }
    printf("%d\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}