Submission #72710404

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define int long long

const int N = 2e5 + 1;
const int M = 998244353;

void solve()
{
    int n;
    cin >> n;
    vector<string> s(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> s[i], s[i] = " " + s[i];
    vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> pre(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> minn(n + 2, vector<int>(n + 2, 1e9));

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            pre[i][j] = pre[i][j - 1] + (s[i][j] == '.');
        }
        for (int j = 0; j <= n; j++)
        {
            f[i][j] = (j - pre[i][j]) + pre[i][n] - pre[i][j];
        }
        // for (int j = n; j >= 1; j--)
        // {
        //     minn[i][j] = min(minn[i][j + 1], f[i][j]);
        // }
    }
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 1e9));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (i == 1)
                dp[i][j] = min(dp[i - 1][j], f[i][j]);
            else
                dp[i][j] = min(dp[i][j], minn[i - 1][j] + f[i][j]);
        }
        for (int j = n; j >= 0; j--)
        {
            minn[i][j] = min(minn[i][j + 1], dp[i][j]);
        }
    }
    int minnn = 1e9;
    for (int j = 0; j <= n; j++)
    {
        minnn = min(minnn, dp[n][j]);
    }
    cout << minnn << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //   cin >> T;

    while (T--)
        solve();

    return 0;
}

Submission Info

Judge Result