#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include //#include "util.h" using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair, ll> Plll; #define PI 3.14159265358979323846 #define EPS 1e-6 #define MIN(a,b) ((a)<(b)?(a):(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define CHAR_BIT 8 #define all(x) (x).begin(), (x).end() template ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { cout << "{" << m.first << ", " << m.second << "}"; return ostr; } template ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { cout << "{ }"; return ostr; } cout << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; } template ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { cout << "{ }"; return ostr; } cout << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { cout << ", " << *itr; } cout << "}"; return ostr; } int N; vector p, q; int ans; void rec(vector& s, int pos) { //全部埋まった if (pos == p.size()) { //順位算出 vector score(N, 0); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (s[i][j] == 'o') score[i]++; } } int rank = 1; for (int w = N - 1; w >= 0; w--) { if (w == score[0]) break; bool flag = false; for (int t = 1; t < N; t++) { if (score[t] == w) flag = true; } if (flag) rank++; } if (ans > rank) ans = rank; return; } *p[pos] = 'o'; *q[pos] = 'x'; rec(s, pos + 1); *p[pos] = 'x'; *q[pos] = 'o'; rec(s, pos + 1); } int yuki0043() { cin >> N; vector s(N); for (int i = 0; i < N; i++) cin >> s[i]; for (int i = 0; i < N - 1; i++) { for (int j = i + 1; j < N; j++) { if (s[i][j] != '-') continue; p.push_back(&s[i][j]); q.push_back(&s[j][i]); } } ans = N; rec(s, 0); cout << ans << endl; return 0; } int main() { //clock_t start, end; //start = clock(); yuki0043(); //end = clock(); //printf("%d msec.\n", end - start); return 0; }