Language: C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){
    for (auto &e : t) fill(e, v);
}

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }



int H, W;
vector<string> fi;
const int MAX_V = 200;
const int MAX = 6;

int sum[MAX_V][MAX_V];
int dp1[MAX_V][MAX_V][MAX_V][2];
int dp2[MAX_V][MAX_V][MAX_V][2];

int solve() {
    // 初期化
    sum[0][0] = 0;
    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            sum[h+1][w+1] = -sum[h][w] + sum[h+1][w] + sum[h][w+1] + (fi[h][w] == '#');
        }
    }
    for (int h1 = 0; h1 <= H; ++h1) {
        for (int h2 = h1; h2 <= H; ++h2) {
            int w2 = 0;
            for (int w1 = 0; w1 <= W; ++w1) {
                if (w2 < w1) w2 = w1;
                while (w2 < W &&
                       (sum[h2][w2+1]-sum[h1][w2+1]-sum[h2][w1]+sum[h1][w1] == 0 ||
                        sum[h2][w2+1]-sum[h1][w2+1]-sum[h2][w1]+sum[h1][w1] == (h2-h1)*(w2+1-w1)))
                    ++w2;
                dp1[h1][h2][w1][0] = w2;
            }
        }
    }
    for (int w1 = 0; w1 <= W; ++w1) {
        for (int w2 = w1; w2 <= W; ++w2) {
            int h2 = 0;
            for (int h1 = 0; h1 <= H; ++h1) {
                if (h2 < h1) h2 = h1;
                while (h2 < H &&
                       (sum[h2+1][w2]-sum[h1][w2]-sum[h2+1][w1]+sum[h1][w1] == 0 ||
                        sum[h2+1][w2]-sum[h1][w2]-sum[h2+1][w1]+sum[h1][w1] == (h2+1-h1)*(w2-w1)))
                    ++h2;
                dp2[h1][w1][w2][0] = h2;
            }
        }
    }

    // dp
    int res = MAX;
    for (int k = 0; k+1 < MAX; ++k) {
        // dp1
        for (int h1 = 0; h1 <= H; ++h1) {
            for (int h2 = h1; h2 <= H; ++h2) {
                for (int w1 = 0; w1 <= W; ++w1) {
                    //cout << k << ", " << h1 << ", " << h2 << ", " << w1 << ": " << dp1[h1][h2][w1][k] << endl;
                    int w = dp1[h1][h2][w1][k%2];
                    chmax(dp1[h1][h2][w1][(k+1)%2], dp1[h1][h2][w][k%2]);
                }
                int w2 = 0;
                for (int w1 = 0; w1 <= W; ++w1) {
                    if (w2 < w1) w2 = w1;
                    while (w2 < W && dp2[dp2[h1][w1][w2+1][k%2]][w1][w2+1][k%2] >= h2)
                        ++w2;
                    chmax(dp1[h1][h2][w1][(k+1)%2], w2);
                }
            }
        }
        
        // dp2
        for (int w1 = 0; w1 <= W; ++w1) {
            for (int w2 = w1; w2 <= W; ++w2) {
                for (int h1 = 0; h1 <= H; ++h1) {
                    // cout << k << "-, " << h1 << ", " << w1 << ", " << w2 << ": " << dp2[h1][w1][w2][k] << endl;
                    int h = dp2[h1][w1][w2][k%2];
                    chmax(dp2[h1][w1][w2][(k+1)%2], dp2[h][w1][w2][k%2]);
                }
                int h2 = 0;
                for (int h1 = 0; h1 <= H; ++h1) {
                    if (h2 < h1) h2 = h1;
                    while (h2 < H && dp1[h1][h2+1][dp1[h1][h2+1][w1][k%2]][k%2] >= w2)
                        ++h2;
                    chmax(dp2[h1][w1][w2][(k+1)%2], h2);
                }
            }
        }

        if (dp1[0][H][0][k%2] == W) chmin(res, k);
        if (dp2[0][0][W][k%2] == H) chmin(res, k);

        for (int x = 0; x < MAX_V; ++x) {
            for (int y = 0; y < MAX_V; ++y) {
                for (int z = 0; z < MAX_V; ++z) {
                    dp1[x][y][z][k%2] = 0;
                    dp2[x][y][z][k%2] = 0;
                }
            }
        }       
    }
    return res;
}

int main() {
    while (cin >> H >> W) {
        fi.resize(H);
        for (int i = 0; i < H; ++i) cin >> fi[i];
        cout << solve() << endl;
    }
}


Compiler output:
a.cc: In function 'int solve()':
a.cc:44:5: error: 'memset' was not declared in this scope
   44 |     memset(dp1, 0, sizeof(dp1));
      |     ^~~~~~
a.cc:3:1: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    2 | #include <vector>
  +++ |+#include <cstring>
    3 | #include <string>