Atcoder

题目：https://atcoder.jp/contests/agc043/tasks/agc043_a

题解

考虑任意一条从点(S)到点(T)的路径(path)，如果(path)含有(t)个连续的'#'块，那么这条路径就需要(t)次操作。举例 (B代表#)：

[BWBWBBW ]

一次操作是针对一个矩形区域，所以任意一条路径都可以拉直来看

这条路径有3个分别连续的'#’块
所以答案就是求所有路径中最小的(t)值。

int main() {

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> maps[i][j];

    for (int i = 0; i <= 100; ++i) dp[i][0] = dp[0][i] = INF;

    dp[0][1] = dp[1][0] = 0;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {
        if (maps[i][j] == '#') {
            dp[i][j] = min(dp[i - 1][j] + (maps[i][j] != maps[i - 1][j]), dp[i][j - 1] + (maps[i][j] != maps[i][j - 1]));
        }
        else {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    /*
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) cout << dp[i][j] << " ";
        cout << endl;
    }
    */
    cout << dp[n][m] << endl;
    return 0;
}