#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 TateMaximumIndependentSet(const Graph& g, const vector& used) { for (int i = 0; i < 2 * N; i++) { if (not used[i]) { vector tmp = used; tmp[i] = true; for (const int to : g.edge[i]) { if (not used[to]) { tmp[to] = true; } } int cnt = 1; for (int j = 2 * N; j < 4 * N; j++) { if (not tmp[j]) { cnt++; } } if (i < N) { if (not tmp[3 * N - 1] and not tmp[4 * N - 1]) { cnt--; } } else { if (not tmp[2 * N] and not tmp[3 * N]) { cnt--; } } ans = max(ans, cnt); } } } void YokoMaximumIndependentSet(const Graph& g, const vector& used) { for (int i = 2 * N; i < 4 * N; i++) { if (not used[i]) { vector tmp = used; tmp[i] = true; for (const int to : g.edge[i]) { if (not used[to]) { tmp[to] = true; } } int cnt = 1; for (int j = 0; j < 2 * N; j++) { if (not tmp[j]) { cnt++; } } if (i < 3 * N) { if (not tmp[N - 1] and not tmp[2 * N - 1]) { cnt--; } } else { if (not tmp[0] and not tmp[N]) { cnt--; } } ans = max(ans, cnt); } } } void TateMaximumIndependentSet2(const Graph& g, const vector& used) { int cnt = 0; for (int i = 0; i < N; i++) { if (not used[i] and not used[i + N]) { cnt++; } } ans = max(ans, cnt); } void YokoMaximumIndependentSet2(const Graph& g, const vector& used) { int cnt = 0; for (int i = 0; i < N; i++) { if (not used[i + 2 * N] and not used[i + 3 * N]) { cnt++; } } ans = max(ans, cnt); } 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); } if (usedv[0] or usedv[N - 1] or usedv[3 * N - 1] or usedv[3 * N]) { } else { ans = 4; } TateMaximumIndependentSet(g, usedv); YokoMaximumIndependentSet(g, usedv); TateMaximumIndependentSet2(g, usedv); YokoMaximumIndependentSet2(g, usedv); cout << ans << endl; return 0; }