算法思路详解

  1. 状态表示选择：三进制状态压缩 由于每个位置存在三种状态，因此采用三进制进行状态压缩，以此来高效表示每一列的整体状态。

  2. 优化状态规模：选择列方向压缩 比较 n 和 m 的大小后，考虑到 3^m 的数值规模过大，无法高效处理，因此最终选择对每一列进行状态压缩，避免状态空间爆炸。

  3. 动态规划（DP）核心流程

    • DP数组定义：dp[i][j] 代表第 i 列的第 j 种合法情况的最小代价。
    • 第一列初始化（边界条件）
      1. 枚举第一列的所有可能状态（最大为 3^4 == 81，时间复杂度可行）。
      2. 通过 check 函数筛选掉列内不合法的状态（即列内上下字母相同的情况）。
      3. 将所有合法状态对应的代价存入 dp[1][j]，完成第一列的初始化。
    • 后续列的状态转移
      1. 对当前列的所有可能状态，先通过 check 函数筛选列内合法状态。
      2. 再通过 check2 函数，寻找与前一列（第 i-1 列）的合法状态能够组合（满足相邻列的约束条件）的所有情况。
      3. 从这些合法组合中筛选出代价最小的情况，执行状态转移，更新 dp[i][j]。
    • 答案求解 遍历最后一列（第 m 列）的所有合法状态对应的 dp[m][j]，其中的最小值即为最终答案。
using ll = long long ; 
using namespace std;
#define endl '\n'
#define pb push_back
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define vi vector<ll>
#define vii vector<vector<ll>>
#define fi first 
#define se second
#define vs vector<string>
#define eb emplace_back
#define in insert
#define pf push_front
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); i++)
const ll inf = 2e18 + 9 ;
const ll mod1 = 1e9 + 7 ; 
const int mod2 = 998244353 ; 
typedef pair<int, int> pll;
typedef long double db;

inline ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;};
inline int read(){int x = 0;short f = 1;char c = getchar();while ((c < '0' || c > '9') && c != '-')c = getchar();if (c == '-')f = -1, c = getchar();while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();x *= f;return x;}
inline ll qsm(ll a , ll b){ll res = 1 ; while(b){if(b & 1){res *= a ; }b >>= 1 ; a *= a ; }return res ; }
int dir[4][2] = {{1 , 0} , {-1 , 0} , {0 , 1} , {0 , -1}};
int dirx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; 
int diry[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int qu(int x , int i)
{
    int j = qsm(3 , i) ;
    return (x / j) % 3 ;
}
bool check(int x , int n)
{
    for(int i = 0 ; i < n - 1 ; i++)
    {
        if(qu(x , i) == qu(x , i + 1))
        {
            return false ; 
        }
    }
    return true ;
}
bool check1(int q , int h , int n)
{
    for(int i = 0 ; i < n ; i++)
    {
        if(qu(q , i) == qu(h , i))
        {
            return false ; 
        }
    }
    return true ;
}
ll cctv(int a1 , int a2 , int a3)
{
    if(!check(a2 , a3))
    {
        return 1e9 ;
    }
    int ans = 0 ;
    for(int i = 0 ; i < a3 ; i++)
    {
        if(qu(a1 , i) != qu(a2 , i))
        {
            ans++ ;
        }
    }
    return ans ;
}
void work() 
{
    int n , m ; cin >> n >> m ;
    vi a(m , 0) ;
    for(int i = 0 ; i < n ; i++)
    {
        string s ; cin >> s ; 
        for(int j = 0 ; j < m ; j++)
        {
            int num ; 
            if(s[j] == 'r')
            {
                num = 0 ;
            }
            else if(s[j] == 'e')
            {
                num = 1 ; 
            }
            else 
            {
                num = 2 ;
            }
            a[j] = a[j] + num * qsm(3 , i) ;
        }
    }
    int num = qsm(3 , n) ;
    vii dp(m , vi(num , inf)) ;
    for(int i = 0 ; i < m ; i++)
    {
        for(int j = 0 ; j < qsm(3 , n) ; j++)
        {
            dp[i][j] = cctv(a[i] , j , n) ;
            if(i != 0 && dp[i][j] != 1e9)
            {
                ll su = inf ;
                for(int k = 0 ; k < qsm(3 , n) ; k++)
                {
                    if(check1(k , j , n))
                    {
                        su = min(su , dp[i - 1][k]) ;
                    }
                }
                dp[i][j] += su ;
            }
        }
    }
    ll ans = 1e9 ; 
    for(int i = 0 ; i < qsm(3 , n) ; i++)
    {
        ans = min(ans , dp[m - 1][i]) ;
    }
    cout << ans << endl ;
}
signed main() 
{
    int t = 1;
    while (t--) 
    {
        work();
    }
    return 0;
}