#include <stdio.h>
int tc;
const int TURE = 1;
const int FALSE = 0;
char map[52][52];
enum {WHITE, BLUE, RED};
int dp[51][3];
int combi[3];
int minChangedColor = 987654321;
void combiAndBacktracking(int order, int beforeIndex, int N, int n_change)
{
if (order == 1)
{
n_change = dp[combi[order - 1]][WHITE];
if (n_change >= minChangedColor)
return;
}
if (order == 2)
{
n_change = n_change + (dp[combi[order - 1]][BLUE] - dp[combi[order - 2]][BLUE]);
if (n_change >= minChangedColor)
return;
n_change = n_change + (dp[combi[order]][RED] - dp[combi[order - 1]][RED]);
if (n_change < minChangedColor)
minChangedColor = n_change;
return;
}
for (int i = beforeIndex + 1; i <= (N - 2) - (2 - (order + 1)); i++)
{
combi[order] = i;
combiAndBacktracking(order + 1, i, N, n_change);
}
}
int main()
{
freopen("input.txt", "r", stdin);
setbuf(stdout, NULL);
scanf("%d", &tc);
for (int testCase = 1; testCase <= tc; testCase++)
{
int N, M;
for (int line = 0; line <= 50; line++)
{
for (int color = WHITE; color <= RED; color++)
{
dp[line][color] = 0;
}
}
minChangedColor = 987654321;
int w = 0;
int b = 0;
int r = 0;
scanf("%d %d", &N, &M);
combi[2] = N - 1;
for (int y = 0; y < N; y++)
{
scanf("%s", map[y]);
for (int x = 0; x < M; x++)
{
switch (map[y][x])
{
case 'W':
w++;
break;
case 'B':
b++;
break;
case 'R':
r++;
break;
}
dp[y][WHITE] = (b + r);
dp[y][BLUE] = (r + w);
dp[y][RED] = (b + w);
}
}
combiAndBacktracking(0, -1, N, 0);
printf("%d\n", minChangedColor);
}
return 0;
}
댓글