페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10407

타일 다시 깔기 40s 1024MB

문제

코디-자말(Cody-Jamal)의 최신 예술 작품은, 다양한 패턴으로 다시 타일을 깔 수 있는 타일 주방 바닥이다. 바닥은 정사각형 타일로 이루어진 \mathbf{R}행 \mathbf{C}열의 행렬 형태이다. 각 타일은 양면이 있어 뒤집을 수 있으며, 한 면은 자홍색(magenta)이고 다른 면은 초록색(green)이다.

주방 바닥을 다시 타일링할 때 사용할 수 있는 연산은 다음 두 가지뿐이다:

  • 타일 하나를 뒤집어, 보이는 색을 자홍색에서 초록색으로(또는 그 반대로) 바꾼다.
  • 인접한 두 타일을(가로 또는 세로로 인접한 경우만, 대각선은 불가) 뒤집지 않은 채로 서로 교환한다.

코디-자말의 예술 바닥을 감상하는 것은 무료지만, 직접 조작하는 것은 유료이다. 타일을 한 번 뒤집는 연산은 \mathbf{F} 코인이 들고, 인접한 타일을 한 번 교환하는 연산은 \mathbf{S} 코인이 든다.

당신은 바닥의 현재 상태를 볼 수 있으며, 이를 특정한 목표 패턴으로 바꾸고 싶다. 목표를 달성하기 위해 필요한 코인의 최소량은 얼마인가?


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 4개의 정수 \mathbf{R}, \mathbf{C}, \mathbf{F}, \mathbf{S}가 주어진다. 이는 각각 바닥의 행 수, 열 수, 타일 뒤집기 연산의 코인 비용, 그리고 타일 교환 연산의 코인 비용이다. 그 다음 2 \cdot \mathbf{R}줄이 이어진다. 처음 \mathbf{R}줄은 각 줄에 \mathbf{C}개의 문자가 있으며, 이 중 i번째 줄의 j번째 문자는 현재 상태에서 i행 j열 타일의 보이는 색을 나타낸다. 문자가 M이면 자홍색이 보이는 것이고, 그 외(즉 G)이면 초록색이 보이는 것이다. 마지막 \mathbf{R}줄도 각 줄에 \mathbf{C}개의 문자가 있으며, 이 중 i번째 줄의 j번째 문자는 i행 j열 타일이 최종적으로 가져야 하는 색을 같은 문자 표기(M/G)로 나타낸다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 타일들의 현재 색 배치를 목표 색 배치로 바꾸기 위해 연산들을 수행할 때 필요한 코인의 최소량이다.


예제 #1

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
테스트 세트 2의 샘플 케이스에서는 뒤집기가 너무 비싸므로 가능한 한 피해야 한다. 원하는 바닥 상태는 현재보다 마젠타 타일이 더 많으므로 최소 한 번의 뒤집기가 필요하다(스왑은 그 수를 바꾸지 못한다). 다음과 같이 한 번의 뒤집기로 최적으로 해결할 수 있다: 왼쪽 끝 두 타일을 스왑한다. 오른쪽 끝 타일을 뒤집는다. 왼쪽에서 두 번째와 세 번째 타일을 스왑한다. 왼쪽에서 세 번째와 네 번째 타일을 스왑한다. 아래 그림은 바닥이 거치는 모든 상태를 보여준다.

예제 #2

1
1 5 1000 1
MGGGG
GGGMM
Case #1: 1003

출처

GCJ 2021r2 D

로그인해야 코드를 작성할 수 있어요.