重要な観察として、あるマスが塗られた時その同じ行の横方向に # を介さずに連結するようなマスについてはすべて塗られている必要があります。 ところで、各行に含まれる # で区切られた連結成分の個数は高々 \(W/2\) 個です。 したがって、各行の塗られ方については各連結成分ごとに塗られずに残っているかどうかをビットで管理することで高々 \(2^{W/2}\) 状態で管理することができます。 この状態ごとに上の行から最大のスコアを保持することで動的計画法を行うことが可能です。

具体的な遷移を考えます。ある行の状態に遷移するためには一つ上の行の状態に対して「少なくともこの連結成分は塗られていてはいけない」という条件が入ります。そのような遷移を愚直に計算すると、遷移の計算量が \(O(2^{W/2})\) となり、全体の計算量が \(O(2^{W})\) となり間に合いません。 しかし、そのような条件は特定の状態の（ビットの意味での）上位集合となるため、例えばゼータ変換などで上位集合についての max を前計算しておくことで各遷移を \(O(1)\) で行うことができます。

以上を適切に実装することにより、時間計算量 \(O(HW 2^{W/2})\) などでこの問題を解くことができます。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i=0; i<(n); i++)
template<typename A, typename B> bool chmax(A &x, B y) {if (x < y) {x = y; return true;} return false;}

int main() {
    ll h,w; cin >> h >> w;
    vector<string> s(h); rep(i, h) cin >> s[i];
    // 行番号を受け取り、（各マスの属する連結成分番号、各連結成分のスコア）を返すヘルパ関数
    auto f = [&] (ll row) -> pair<vector<ll>, vector<ll>> {
        vector<ll> c(w, -1), a;
        ll cnt(-1);
        rep(i, w) {
            if (s[row][i] == '#') continue;
            if (i == 0 || s[row][i-1] == '#') {cnt++; a.emplace_back(0);}
            c[i] = cnt;
            a[cnt] += (s[row][i] == '+' ? 1 : -1);
        }
        return {c, a};
    };
    // 上位集合についてのmaxをとる
    auto superset_max = [&] (vector<ll> &dp) {
        ll k = __builtin_ctzll(dp.size());
        rep(i, k) {
            rep(bit, (1ll << k)) if (((bit >> i) & 1) == 0) chmax(dp[bit], dp[bit ^ (1ll << i)]);
        }
        return dp;
    };
    vector<ll> dp;
    auto [c, a] = f(0);
    ll k = a.size();
    rep(bit, (1ll << k)) {
        dp.emplace_back(0);
        rep(i, k) if ((bit >> i) & 1) dp[bit] += a[i];
    }
    superset_max(dp);
    for (ll i=1; i<h; i++) {
        auto [c, a] = f(i-1);
        auto [cn, an] = f(i);
        ll k = an.size();
        vector<ll> dpn(1ll << k, 0);
        rep(bit, 1ll << k) {
            ll bn(0);
            rep(i, w) {
                if (c[i] == -1 || cn[i] == -1 || (((bit >> cn[i]) & 1) == 0)) continue;
                bn |= (1ll << c[i]);
            }
            rep(i, k) if ((bit >> i) & 1) dpn[bit] += an[i];
            dpn[bit] += dp[bn];
        }
        swap(dp, dpn);
        superset_max(dp);
    }
    cout << dp[0] << "\n";
}