#include #include using namespace std; using namespace atcoder; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector S(N); for (int i = 0; i < N; i++) { cin >> S[i]; } vector> W, T; // 白マス for (int i = 0; i < N; i++) { for (int j = 0; j < 2 * N; j++) { if (S[i][j] == '.') { W.push_back({i, j}); } } } // 目標マス(左半分) for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { T.push_back({i, j}); } } int K = N * N; int s = 2 * K; int t = 2 * K + 1; mcf_graph g(2 * K + 2); for (int i = 0; i < K; i++) { g.add_edge(s, i, 1, 0); } for (int j = 0; j < K; j++) { g.add_edge(K + j, t, 1, 0); } for (int i = 0; i < K; i++) { auto [r1, c1] = W[i]; for (int j = 0; j < K; j++) { auto [r2, c2] = T[j]; ll cost = abs(r1 - r2) + abs(c1 - c2); g.add_edge(i, K + j, 1, cost); } } auto ans = g.flow(s, t); cout << ans.second << '\n'; }