AtCoder AGC043A Range Flip Find Route

题意
给一个$n\cdot m$的矩阵，’.’表示白色，’#’表示黑色，需要从$(1,1)$走到$(n,m)$，只允许走右方和下方，且只能经过白色方块，每次操作可以将一个小矩阵中的黑白互换，问最小操作数使得可以从$(1,1)$走到$(n,m)$

分析

对于任意一条路径来说，是黑白相间的，由于只能走右方和下方，对于一段黑色路径，一定可以经过一次操作，使得所有的黑色变为白色，且可以发现，对于隔着一段白色路径的两段黑色路径，一定不能只经过一次操作就可以将这两段黑色路径同时变为白色路径

因此对于任意一条路径来说，最小操作数即为这条路径的连续黑色路径数

可采取$DP$，$dp[i][j]$表示从$(1,1)$到$(i,j)$的最小操作数，如果$(i,j)$是白色方块，$(i,j+1)$或$(i+1,j)$是黑色方块，则从$(i,j)$到$(i+1,j)$或$(i,j+1)$的路径的连续黑色路径数加一，但由于最小操作数是取所有路径的最小操作数，取$\min$即可

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
char a[105][105];
int dp[105][105];
const int dirx[] = {0, 1};
const int diry[] = {1, 0};

void solve() {
    int n, m;
    cin >> n >> m;
    rep(i, 1, n)cin >> (a[i] + 1);
    memset(dp, 0x3f, sizeof(dp));
    dp[1][1] = a[1][1] == '#';
    rep(i, 1, n) {
        rep(j, 1, m) {
            rep(k, 0, 1) {
                int x = i + dirx[k];
                int y = j + diry[k];
                if (x <= n && y <= m)
                    dp[x][y] = min(dp[x][y], dp[i][j] + (a[i][j] == '.' && a[x][y] == '#'));
            }
        }
    }
    cout << dp[n][m];
}

signed main() {
    start;
    while (T--)
        solve();
    return 0;
}