SRM 553 div1 med TwoConvexShapes

問題

TopCoder Statistics - Problem Statement

N*M のグリッドを考える。セルのいくつかはすでに黒色か白色に塗られている。残りの箇所を, 以下の性質を満たすように塗りたい。

• 各色のセルは連結である。
• 各色のセルは凸である。ここで, 凸とは, 各行, 各列について, あるセルの色の両方向に別の色が存在しないことを言う(例えば BWB とかは W が B に挟まれているのでダメ)。

色の塗り方は何通りあるか求めよ。

解法

サンプルが通っただけでまだシステムテストは走らせてないのであってるかわかりません。

4 方向くるくる回転させながら, 条件を満たす塗り方を数え上げれば良いです。

4 方向について回転させる場合, 実は上記の場合分けだけですべて尽くされています(しかもダブりがない！)。
やけに「左下は塗らない」ことにこだわっていますが, これがないと「左上の角だけ塗る場合」と「左上と右上を塗る場合」を 90 度回転させた場合とかでダブってしまいます。

const int MOD = 1e9+7;

class TwoConvexShapes {
public:
    vector<string> rotate(vector<string> grid) {
        int n = grid.size(), m = grid[0].size();
        vector<string> ret;
        for (int i = 0; i < m; i++) {
            string s;
            for (int j = n-1; j >= 0; j--) {
                s += grid[j][i];
            }
            ret.push_back(s);
        }
        return ret;
    }
    ll count0(vector<string> grid, char c) {
        int n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            if (grid[i][j] != c && grid[i][j] != '?') return 0;
        }
        return 1;
    }
    // 左上だけは c で塗られていることが保証されているような塗り方の数
    // 左下は塗らない
    ll count1(vector<string> grid, char c) {
        int n = grid.size(), m = grid[0].size();
        // 準備
        ll dp[55][55];
        memset(dp, 0, sizeof(dp));
        // high: c がある最後列
        // low: !c がある最前列
        int high[55], low[55];
        memset(high, 0, sizeof(high));
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                if (grid[i][j-1] == c) high[i] = j;
            }
            low[i] = m+1;
            for (int j = m; j >= 1; j--) {
                if (grid[i][j-1] != c && grid[i][j-1] != '?') low[i] = j;
            }
            if (low[i] < high[i]) return 0;
        }
        // dp
        for (int i = max(high[0], 1); i < min(low[0], m); i++)
            dp[0][i] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = high[i]; j < min(low[i], m); j++) {
                for (int k = j; k < m; k++)
                    (dp[i][j] += dp[i-1][k]) %= MOD;
            }
        }
        return dp[n-1][0];
    }
    ll count2(vector<string> grid, char c) {
        int n = grid.size(), m = grid[0].size();
        // 0: 高さ維持
        // 1: 高さ広義の単調減少
        // 2: 高さ広義の単調増加
        ll dp[55][55][3];
        memset(dp, 0, sizeof(dp));
        int high[55], low[55];
        memset(high, 0, sizeof(high));
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                if (grid[i][j-1] == c) high[i] = j;
            }
            low[i] = m+1;
            for (int j = m; j >= 1; j--) {
                if (grid[i][j-1] != c && grid[i][j-1] != '?') low[i] = j;
            }
            if (low[i] < high[i]) return 0;
        }
        // dp
        for (int i = max(high[0], 1); i < min(low[0], m); i++)
            dp[0][i][0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = high[i]; j < min(low[i], m); j++) {
                dp[i][j][0] = dp[i-1][j][0];
                dp[i][j][1] = dp[i-1][j][1];
                for (int k = j+1; k < m; k++) 
                    (dp[i][j][1] += dp[i-1][k][0] + dp[i-1][k][1]) %= MOD;
                dp[i][j][2] = dp[i-1][j][2];
                for (int k = 1; k < j; k++)
                    (dp[i][j][2] += dp[i-1][k][0] + dp[i-1][k][2]) %= MOD;
            }
        }
        ll ret = 0;
        for (int i = 1; i < m; i++) {
            (ret += dp[n-1][i][0]+dp[n-1][i][1]+dp[n-1][i][2]) %= MOD;
        }
        return ret;
    }
    void print(vector<string> grid) {
        for (string s : grid)
            cout << s << endl;
        cout << endl;
    }
    int countWays(vector <string> grid) {
        ll ret = 0;
        for (int i = 0; i < 4; i++) {
            print(grid);
            (ret += count1(grid, 'B')) %= MOD;
            cout << ret << endl;
            (ret += count1(grid, 'W')) %= MOD;
            cout << ret << endl;
            (ret += count2(grid, 'B')) %= MOD;
            cout << ret << endl;
            grid = rotate(grid);
        }
        ret += count0(grid, 'W') + count0(grid, 'B');
        return ret;
    }
}

解法についてはすぐなんとなく察するんですがうまくコードに出来ないなぁというやつ。