만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

러시아 국기 만들기

면접 대비

시간 제한2초메모리 제한512 MB

요약
흰색, 파란색, 빨간색 띠 경계가 되는 두 행을 정해 다시 칠할 칸 수를 가장 작게 만듭니다.
난이도

쉬움10점 중 3점

유형
완전 탐색, 누적 합
정답자
아직 제출이 없습니다

문제

2016년 국제정보올림피아드는 러시아에서 열린다.

러시아 국기는 가로 띠 세 개로 나뉜다. 맨 윗줄은 흰색, 가운데 줄은 파란색, 맨 아랫줄은 빨간색이다.

선생님이 N×MN \times M 격자판을 가져왔다. 격자판의 각 칸은 흰색, 파란색, 빨간색 중 하나로 칠해져 있다. 이 격자판을 러시아 국기 모양으로 바꾸는 것이 과제다.

규칙은 다음과 같다.

  1. 칸 하나를 골라 원하는 색으로 다시 칠할 수 있다.
  2. 다 칠하고 나면 위쪽 부분은 전부 흰색, 가운데 부분은 전부 파란색, 아래쪽 부분은 전부 빨간색이어야 한다. 세 부분은 각각 한 줄 이상을 차지한다.
  3. 다시 칠하는 칸의 수는 최소여야 한다.

규칙을 지키면서 러시아 국기 모양으로 만들 때 다시 칠해야 하는 칸의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 NN과 MM이 공백으로 구분되어 주어진다. (3≤N≤503 \le N \le 50, 3≤M≤503 \le M \le 50)

다음 NN개 줄에 길이가 MM인 문자열이 한 줄씩 주어진다.

각 문자열은 대문자 "W", "B", "R"로만 이루어진다. "W"는 흰색, "B"는 파란색, "R"은 빨간색이다.

출력

러시아 국기 모양으로 만들기 위해 다시 칠해야 하는 칸의 최소 개수를 출력한다.

예제4

  1. 예제 1

    입력
    4 5
    WRWRW
    BWRWB
    WRWRW
    RWBWR
    
    예상 출력
    11
    
  2. 예제 2

    입력
    6 14
    WWWWWWWWWWWWWW
    WBBBWWRRWWBBBW
    WWBWWRRRRWWBWW
    BWBWWRRRRWWBWW
    WBBWWWRRWWBBBW
    WWWWWWWWWWWWWW
    
    예상 출력
    44
    
  3. 예제 3

    입력
    3 3
    WWW
    BBB
    RRR
    
    예상 출력
    0
    
  4. 예제 4

    입력
    3 3
    RRR
    BBB
    WWW
    
    예상 출력
    6