#include #define VARNAME(x) #x #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using ld = long double; template vector Vec(int n, T v) { return vector(n, v); } template auto Vec(int n, Args... args) { auto val = Vec(args...); return vector(n, move(val)); } template ostream& operator<<(ostream& os, const vector& v) { os << "sz:" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = (ll)1e9 + 7LL; constexpr ld PI = static_cast(3.1415926535898); template constexpr T INF = numeric_limits::max() / 10; struct Graph { Graph(const int n) { edge.resize(n); } void addEdge(const int from, const int to) { edge[from].push_back(to); edge[to].push_back(from); } vector> edge; }; int N; int ans; void MaximumIndependentSet(const Graph& g, const vector& used, const int use, const int res) { if (ans == N + 1) { return; } if (use + res <= ans) { return; } ans = max(ans, use); for (int i = 0; i < 4 * N; i++) { if (not used[i]) { vector tmp = used; tmp[i] = true; int tmpres = res - 1; for (const int to : g.edge[i]) { if (not used[to]) { tmpres--; tmp[to] = true; } } MaximumIndependentSet(g, tmp, use + 1, tmpres); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; vector ok(4 * N, true); vector> room(N, vector(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { char c; cin >> c; room[i][j] = c == '.'; } } Graph g(4 * N); int res = 4 * N; vector usedv(4 * N, false); for (int i = 0; i < 4 * N; i++) { const bool tate1 = i < 2 * N; const int offset1 = (i % (2 * N)) / N; const int pos1 = (i % (2 * N)) % N; for (int k = 0; k < N - 1; k++) { if (tate1) { if (not room[offset1 + k][pos1]) { res--; usedv[i] = true; break; } } else { if (not room[pos1][offset1 + k]) { res--; usedv[i] = true; break; } } } } for (int i = 0; i < N; i++) { if (usedv[i]) { continue; } g.addEdge(i, i + N); if (i == 0) { for (int j = 2 * N; j < 3 * N; j++) { if (usedv[j]) { continue; } const int y = (j - 2 * N) % N; if (y < N - 1) { g.addEdge(i, j); } } } else if (i < N - 1) { for (int j = 2 * N; j < 4 * N; j++) { if (usedv[j]) { continue; } const int y = (j - 2 * N) % N; if (y < N - 1) { g.addEdge(i, j); } } } else { for (int j = 3 * N; j < 4 * N; j++) { if (usedv[j]) { continue; } const int y = (j - 2 * N) % N; if (y < N - 1) { g.addEdge(i, j); } } } } for (int i = N; i < 2 * N; i++) { if (usedv[i]) { continue; } if (i == 2 * N) { for (int j = 2 * N; j < 3 * N; j++) { if (usedv[j]) { continue; } const int y = (j - 2 * N) % N; if (y > 0) { g.addEdge(i, j); } } } else if (i < 2 * N - 1) { for (int j = 2 * N; j < 4 * N; j++) { if (usedv[j]) { continue; } const int y = (j - 2 * N) % N; if (y > 0) { g.addEdge(i, j); } } } else { for (int j = 3 * N; j < 4 * N; j++) { if (usedv[j]) { continue; } const int y = (j - 2 * N) % N; if (y > 0) { g.addEdge(i, j); } } } } for (int i = 2 * N; i < 3 * N; i++) { if (usedv[i] or usedv[i + N]) { continue; } g.addEdge(i, i + N); } MaximumIndependentSet(g, usedv, 0, res); cout << ans << endl; return 0; }