#include #include using namespace std; #define N 6 int n; char s[N][N]; int rank() { int w[N] = { 0, }; for ( int i = 0; i < n; i++ ) { for ( int j = 0; j < n; j++ ) { w[i] += s[i][j] == 'o' ? 1 : 0; } } int t[N] = { 0, }; for ( int i = 0; i < n; i++ ) { t[w[i]] = 1; } int r = 0; for ( int i = w[0]; i < n; i++ ) { r += t[i]; } return r; } int dfs(int a, int b, int r, int rg) { s[a][b] = r ? 'o' : 'x'; s[b][a] = r ? 'x' : 'o'; int mn = N; if ( rg == 1 ) { mn = ::rank(); } else { int t = b; for ( int i = a; i < n - 1; i++ ) { for ( int j = t + 1; j < n; j++ ) { if ( s[i][j] == '-' ) { mn = min(min(dfs(i, j, 1, rg - 1), dfs(i, j, 0, rg - 1)), mn); } } t = i + 1; } } s[a][b] = s[b][a] = '-'; return mn; } int main() { int rg = 0; cin >> n; for ( int i = 0; i < n; i++ ) { for ( int j = 0; j < n; j++ ) { cin >> s[i][j]; rg += s[i][j] == '-' ? 1 : 0; } } rg /= 2; if ( rg == 0 ) { cout << ::rank() << endl; return 0; } for ( int i = 0; i < n - 1; i++ ) { for ( int j = i + 1; j < n; j++ ) { if ( s[i][j] == '-' ) { cout << min(dfs(i, j, 1, rg), dfs(i, j, 0, rg)) << endl; return 0; } } } return 0; }