Tác phẩm mới nhất của Cody-Jamal là một sàn bếp lát gạch có thể đổi sang nhiều hoa văn. Sàn là ma trận \(R\) hàng, \(C\) cột các viên gạch vuông. Mỗi viên có thể lật: một mặt màu magenta (M), mặt kia màu xanh (G).

Có hai thao tác:

• lật một viên, đổi màu nhìn thấy từ magenta sang xanh hoặc ngược lại;
• hoán đổi hai viên kề cạnh theo ngang hoặc dọc, không theo đường chéo, mà không lật chúng.

Xem sàn miễn phí, nhưng thao tác thì không: một lần lật tốn \(F\) xu, một lần đổi chỗ tốn \(S\) xu. Bạn biết trạng thái hiện tại và hoa văn đích. Cần ít nhất bao nhiêu xu?

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Dòng đầu mỗi bộ chứa \(R,C,F,S\). Tiếp theo là \(2R\) dòng, mỗi dòng \(C\) ký tự. \(R\) dòng đầu là trạng thái hiện tại; \(R\) dòng cuối là trạng thái mong muốn. Ký tự M nghĩa là mặt magenta đang hiện, G nghĩa là mặt xanh.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(y\) là số xu ít nhất để biến trạng thái hiện tại thành trạng thái đích.

Ràng buộc

• \(1\le T\le100\); \(1\le R,C\le10\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(F=S=1\).
• Test Set 2 (Hidden Verdict): \(1\le F,S\le10^6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
2 4 1 1
MGMG
MMMG
GMGM
MMMM
3 3 1 1
MGG
GMG
MMM
MMM
MGM
MMG

Case #1: 3
Case #2: 4

Ví dụ bổ sung — Test Set 2

??? "Giải thích"
    Ví dụ này không được chạy trên lời giải nộp.

    !!! question "Ví dụ 2"
        ???+ "Input"
            ```sample
            1
            1 5 1000 1
            MGGGG
            GGGMM
            ```
        ???+ success "Output"
            ```sample
            Case #1: 1003
            ```
        ??? "Giải thích"
            Lật rất đắt nên phải tránh tối đa. Tuy nhiên, đích có nhiều ô magenta hơn hiện tại nên cần ít nhất một lần lật, vì đổi chỗ không thay đổi số lượng. Cách tối ưu: đổi hai ô trái nhất; lật ô phải nhất; đổi ô thứ hai và ba từ trái; đổi ô thứ ba và tư từ trái.

            ![Năm trạng thái sàn của mẫu Test Set 2](https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_00c0feba.png)

Nguồn

Google Code Jam 2021, Vòng 2, bài Retiling.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.